You can use a symmetric cipher (AES is the current standard), and exchange keys via Diffie-Hellman key exchange, which is a method of securely generating a shared private cipher key over a public channel.
As I understand it, the primary advantage of public key cryptography is that it makes encryption and decryption asymmetric processes - i.e. everyone can encrypt something using your public key, but only you can decrypt it, because only you know your private key. In the phone case, the asymmetry would actually be annoying, because both parties want to send encrypted messages to each other, so you'd have to deal with two key pairs for each phone conversation.
See http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exch... and http://en.wikipedia.org/wiki/Advanced_Encryption_Standard .
A year of 9600 baud is ~36.1 GB.
Hand-deliver a flash stick once a year.
Obviously this is not a solution for everyday telephony between strangers. But RSA could be.
> nobody cares who listens to their conversations
This is true mostly because seriously caring is at present impractical.
There's absolutely no way to get security without some sort of verification by the user. At the very least, you need someone to verify that the keys are correct "can you read me your phone's security serial?". It shouldn't be too hard to create affordable, usable phones based on PKC. The problem is that nobody cares who listens to their conversations, because it's all "where are we meeting tonight/that movie was shit/i can't believe X did Y".