I've not managed to read all the comments in this post, so apologies if I'm repeating other people, I also have only a passing understanding of how Google Play works, but couldn't we have:
Linux based phone, running Anbox to support Android apps running within containers. Effort would then have to put into support Play APIs within Anbox. Not a small amount of work, but I compare it to the state of Linux 20 years ago and how well Linux is doing today.
Yes. This already exists (though usually with Waydroid rather than Anbox I think). My Ubuntu Touch phone can run Android apps via Waydroid.
The integration isn't perfect (some important things like forwarding notifications to the host system are still missing) but it's already further along than you might have imagined.
Google would eventually manage to completely block that. For example, have the app be encrypted for download from the Play Store for the individual Google-approved device key, and the device’s firmware will decrypt and run the app in a way so that the user can’t get hold of the decrypted app blob, and hence can’t possibly run it in any other (non-Google-approved) environment.
The bottom line is, the only way to ensure user freedom here is by regulation/legislation.
The regulation will only work if it is clear that an alternative is viable and usable. This is why it's important to use GNU/Linux on mobile today.