Tried a VPN into Dallas, deleting previous builder, and deploying. That initially failed with:
WARN Failed to start remote builder heartbeat: failed building options: failed probing “$ORGNAME”: context deadline exceeded
Error: failed to fetch an image or build from source: error connecting to docker: failed building options: failed probing “$ORGNAME”: context deadline exceeded
But then I tried it again, and it appears to be building! 
Aaaaaand – there it goes, deploy successful.
So – for anyone wondering – yes, it looks like you can use a VPN to poke around for regions with capacity until they can do that for you automatically.
(Note that in my case, I had to deactivate my internal Fly Wireguard VPN to activate my commercial, consumer web traffic VPN product – but I think it’d probably be possible to use just Fly for this bit as well)