As an alternative to GCM, you could use MQTT as an open source and popular push notification alternative when Google account and Google Play services are absent on the device. Facebook has used aspects of MQTT in Facebook Messenger.
MQTT implementation requires:
1) an MQTT broker which runs on the server side. This could be something like the mosquitto broker which is Open Source.
2) an MQTT client library which you include in your Android app, enabling your app to connect, subscribe, and publish messages. There are a number of Java options listed at http://mqtt.org/software
3) to come up with a way of uniquely identifying users or devices, and then use that as a topic so that you can individually publish a message to one device.
Dale Lane has written a nice guide on this (http://dalelane.co.uk/blog/?p=1599) and there is also a good set of resources about MQTT (https://github.com/mqtt/mqtt.github.io/wiki)
Also the blog post Github sample below provides a practical example to implement MQTT push notification for Android:
http://tokudu.com/post/50024574938/how-to-implement-push-notifications-for-android
https://github.com/tokudu/AndroidPushNotificationsDemo