Google Compute Engine offers a free f1-micro VM (free forever tier).
Provision it using the Debian GNU/Linux 9 (stretch) image.
Add a static public IP for this instance.
Installation of Pihole was flawless using the curl/bash command-line. Use Google DNS as the backend resolver.
Add a firewall rule (using the Google Cloud VPC network settings) to allow public DNS queries (allow 0.0.0.0/0 to access TCP/UDP port 53) for this instance. If you are only using Google cloud to run this little instance, then you might as well apply this firewall rule to all instances in your VPC instead of specifying which instances the firewall rule is applicable to (which may require you to tag instances etc.).
Replace the DNS server entry in /etc/resolv.conf on this instance with 127.0.0.1.
Test out the Pihole resolver from your home computer by setting the instance's public IP to be your DNS server in your TCP/IP settings.
To ensure I am always using it, I added the public IP of this instance to my wi-fi router. But the wi-fi router was still adding itself as a secondary DNS server and there was no way to override it. So, sometimes, since the latency to the Google instance was obviously greater, my computer was using the wi-fi router as the DNS server which was in-turn getting its DNS queries resolved via the ISP. Not good.
But there was an easy fix. In the router's WAN settings, I updated the DNS server to be again the Pihole. So, even if my home computer was referring to the router's IP address as the DNS server, I was still able to use Pihole.
Now that the home network was ad-blocked, the next step was to ad-block my phone, no matter which network I was using.
I installed the DNS Changer app ( https://play.google.com/store/apps/details?id=com.burakgon.dnschanger&hl=en_US) on my Android phone. This app creates a virtual VPN which uses your specified DNS server on all networks (even on mobile data). Keep the VPN running, it doesn't consume much in terms of CPU/RAM.
This is working beautifully so far.
There was a hiccup when Pihole showed "0 domains blocked" for some reason. I just updated the gravity (query lists) again and all was well.
The easiest way to test was to to go to an ad-block test site, or to nslookup retailwith.com. It should return 0.0.0.0.
It has been running for a few days now, and the cpu usage on the google instance is less than 0.1%. I see many clients depending on how many IP addresses my phone gets as it roams through cell towers.
Hope you find it useful.