U.S. Senator Ron Wyden warned that foreign governments are spying on smartphone users by compelling Apple and Google to turn over push notification records
I guess that would explain the difficulties some apps face without push notifications and releasing APKs. These big companies want you to rely on their systems. Signal was pushing their app through play store. I don't know if an equivalent exists, but it really needs to. We need this, combined with f-droid, so we don't have to use spyware like the Play Store.
Signal does in fact distribute an APK that isn't dependant on Play Services/FCM on their website. Uses a websocket, so not the most elegant way I guess, but oh well.
It's rather hidden, which I think is disappointing. But it exists. Updates itself, too.