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.