Developers could band together, build one such app that does the communication part and forwards any incoming message to the right destination using intents. (ie what GCM does)
On the phone they could then look if GCM is around (and use it) or if that other notification app is around (and use it) or propose to install said app. It's negligible in terms of user confusion because people on non-GCM systems likely know what they're getting into (except for those using Amazon Fire).
That still wouldn’t solve the problems of many open source devs.
I, for example, develop an app connecting to servers that the users self-host.
I can’t modify the server, nor can I easily get it to send notifications.
But I want to be able to show notifications.
Luckily I can open a port to it and wait for them.
It’s impossible to solve with GCM.
XMPP supports that, so it should be possible to provide an optional extension to your protocol to do likewise.
Well, the actual drawback is that you end up with over a dozen such notifications, your entire UI is full with them, and there’s no way to get rid of them, even if you developed the apps yourself.