Additionally it is already possible to download APKs as they are hosted on Google Play from sites like apkmirror.com and you can even install the Play Store if you have microG and are so inclined.
There's no lack of app distribution :-)
I think it would be cool to implement a similar system on top of the Web Push API. This overs e2e encrypted push with existing clients. We would just need to define the Java client API.
Notably absent is a method for connecting that HTTP API to the JavaScript receiver. This is independent of the Web Push protocol and how it is implemented will affect the performance. For example Chrome on Android will use Google's regular push infrastructure (or at least a wrapper around it) and will have the same performance. You could implement this part via polling but the performance will be terrible.
So to make a replacement for Google's push system on Android you would need to rewrite 1 and 2 (possibly just translating the JavaScript browser API to Java) and you would need a push server implementation as well as a client to run on the phone. This client is where you take care. But as long as you run one client per device it should perform similarly to Google's solution. The main problem would be if every app ran their own client, but that isn't what is expected. The phone should provide the push server information to the app (which hands it over to the server) so that all apps on the device use the same server.
Sure, you are still implementing a lot, but the thing is that websites and services already have ways to store these push endpoints in the DB as well as encrypting the messages and sending them. It would be a lot less work to get them to do a little client-side work so that they app uses the same codepath as their webapp than making changes to their whole stack to support a new protocol.
"Apps or third party code (e.g., SDKs) that download executable code, such as dex files or native code, from a source other than Google Play."
If someone thinks it's an overreach, read about cases when apps were banned due to a link to another Google Play app from the same developer [1]
[1] https://www.reddit.com/r/androiddev/comments/atsju7/linking_...