I haven't actually worked with GCM so please forgive me if this doesn't make any sense. I suggest that, instead of routing all messages through GCM, what if Signal could send a "wake up" message via GCM, and then let the app pull the encrypted messages directly out of Signal's servers? A wake up message would only be sent by the server if the message could not be received by the client via normal means (implying that the device is asleep).

An optional user preference could allow some dummy wake up messages to be sent at random moments during the day, to support plausible deniability, at the cost of slightly worse battery life performance. This would all happen silently and the user would only notice a message notification when the app successfully fetches a new incoming message.