Just a heads-up, you can get 1 CPU and 0.6 gigs of RAM for free with the new entry tier of GCP: https://cloud.google.com/free/

(Disclaimer: Google employee, unrelated product area)

Notwithstanding the irony of one google service hurting another, the free tier only has 1GB of free egress traffic right?

Dang, you're right, I forgot about that. So not so suitable, unfortunately.

Seems like root + a local hosts adblocker is still the best solution for Android, or a local VPN for iOS (do they have those on Android? never checked).

I don't have a full understanding of what's going on here, so this might be a stupid comment: Isn't 1GB of DNS lookups quite a lot?

Geez, color me double-wrong. Yes, that should be plenty. I thought was a VPN-esque solution that required shuffling all traffic through the VPS instance, but yes you're right, it's basically just a custom DNS server. In which case this would be totally fine. I might even try it myself if I ever decide to unroot my phone.

DNS66 (https://github.com/julian-klode/dns66) doesn't require root. It uses the Android VPN system to capture DNS requests and forwards everything else.