This is called "Split Horizon DNS". The problem is, there is no standard way to communicate this information to a machine. e.g., afaik there is no DHCP extension to say "for .internal, please see this server, for the rest, see whatever". So you pretty much have to run a server in the middle.
It -is- possible, as others have commented, to do this within the VM or container but they need a way to get that information. systemd-resolved does this. From what I understand of fly.io, the container is setup by the user, so you're not going to have control over their networking configuration or environment - is that right?
Now there is an alternative, which is instead of using .internal, to use a public facing internet hosting that is delegated to your internal DNS servers. That way they use their normal DNS, and it resolves to your nameserver. But the DNS needs to be public, and critically, if the internet DNS goes down, your .internal resolution will also stop working. Which is highly likely to cause problems for peoples applications. And also adds un-predictable latency to their local service connections which is almost certainly going to cause problems - it's not a good idea.
Having said all of that, generally speaking, it makes sense that -you- provide the DNS. It's pretty much the standard way that your 'ISP', 'Hosting Provider', etc, provides the DNS rather than relying on the public internet DNS. Only a few years ago there was no such public DNS.
The other possible alternative would be to leverage multicast DNS (libnss-mdns/avahi-daemon) or LLMNR but I'm not sure those are really ideal for this use case either. And in both cases requires resolver support that you dont get from the basic glibc resolver. So for your use case, may still not be workable.
So I think you're stuck, unless you can mandate that all of your VM images use systemd-resolved and somehow communicate the config into them.