If SSL is not acceptable for my app to communicate with the client, how should I encrypt the traffic? I need something fast (so public key algorithms are out of question). I was thinking about One Time Password, but the problem is that I can not store a very long key on the mobile app because of app size restrictions. What would you recommend?
How do you know that SSL isn't acceptably fast? Have you benchmarked it? As David said, SSL only uses public-key cryptography for the setup and to establish a shared secret, which is then used as the key to quick symmetric algorithms. So before you reject SSL, you should actually test it first.