Do traffic-analysis-resistant wasteful routing among "servers". Run constant-bandwidth from the server to the client to foil traffic analysis if you really care about that (say, messages delivered only every polling window, and every polling window, a communications of the same size/direction. That seems pretty impractical on mobile, though, so maybe use some kind of push protocol for "you have a new chat request" and then foiling traffic analysis within the chat session (when you're actively using the device). Unfortunately if you can monitor all of the network, an attacker could identify a recipient just by initiating a request and watching for a new chat opening. You could also do things like block off known travel times or other times when someone won't be in contact, correlate with message response times, and at least be able to rule in or out certain suspects (it won't help in fishing expeditions, but if you have 10k people it might be, you could probably identify a person in a few months of passive analysis).
In short, low-latency is the enemy of traffic analysis protection. A true surveillance proof system looks more like anonymous remailers and less like Tor. But, people want realtime.
This way, not only would the message content be safe from pyring eyes, but nobody would be able to see who is talking to who or when.
Sure, you need to rely on Tor, but aside from that anybody could set up their own server easily (no hassle with DNS and SSL certs).