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).