Buenas, el Google Cloud Messaging es gratuito totalmente. Existen límites del tamaño y número de mensajes en cola (es decir, no entregados todavía pero que GCM guarda para cuando el móvil destino se conecte). Aun así son tan elevados que no vas a superarlos.