I think the impedance mismatch here is I am assuming we are talking about a hyperscaler cloud where it would be reasonable to have say 1024 proxies per region. Each app would be assigned to 4/1024 proxies in each region.
I have no idea how big of a compute footprint fly.io is, and maybe due to that the design I am suggesting makes no sense for you.