Every network that carries your communication gets the metadata.

In this case, it seems like that metadata would 'just' be the time you sent and received messages from the server. Depending on how Google's push protocol works.

So for the average person that would be fine, but if you were seriously annoying a government that was in bed with your phone company, they could probably figure out who was a part of your cell by the timing of your sent and received messages.

I don't know, but I would have guessed that Google needs to know when it should deliver a message and where it should go, no? That is metadata in my definition.

GCM payloads are fully encrypted. Google would be able to tell that you are a TextSecure user who is receiving a message, but they cannot tell who the message is coming from nor can they look at its contents (obviously).

But crucially, this will still be vulnerable to timing attacks, if I'm not mistaken.

What's the specific timing attack you're considering here?

There may not be the traditional byte at a time comparison type timing attack, but maybe this is still vulnerable to timing correlation attacks in the same sense that tor is. That is, Google or someone monitoring Google's network can look at all the messages and see who is talking to whom by matching up timing and encrypted message bodies.

I'm guessing: I send a message, you receive a message -> possible to infer (with some confidence) that I messaged you?

(I don't know if that would be feasible, but I suppose that's what avn2109 meant).

[ie: not a timing attack, but traffic analysis]

Good point. I did indeed mean traffic analysis, not "timing attack."