> because the public key has to be hardcoded in the app binary

Nope. On iOS the flow is:

1. Generate a "push token" on the device (with the user's approval).

2. Send this token to your server.

3. Now you can send notifications to the device via this token. Your server needs to authenticate itself with Apple, and this requires an Apple account. But it's not linked to an individual app.

The situation is different on Android. Google went out of their way to make it impossible to customize `google-services.json` at runtime. So the built-in "easy" flow won't work. But notifications ultimately work using veeeeery obfuscated remote procedure calls to Google Play Services and you can run them manually. I need to do a write-up about this....