I'm no security expert, but I don't think you even need an out-of-band key exchange mechanism. Just use public key cryptography [1], as used in SSH/TLS/PGP/GPG.
I was about to write this response, but I see that it is more clearly written in the wikipedia article already:
Another potential security vulnerability in using asymmetric keys is the possibility of a man-in-the-middle attack, in which communication of public keys is intercepted by a third party and modified to provide different public keys instead. Encrypted messages and responses must also be intercepted, decrypted and re-encrypted by the attacker using the correct public keys for different communication segments in all instances to avoid suspicion. This attack may seem to be difficult to implement in practice, but it's not impossible when using insecure media (e.g. public networks such as the Internet or wireless communications). A malicious staff member at Alice or Bob's ISP might find it quite easy to carry out. In the earlier postal analogy, Alice would have to have a way to make sure that the lock on the returned packet really belongs to Bob before she removes her lock and sends the packet back. Otherwise the lock could have been put on the packet by a corrupt postal worker pretending to be Bob to Alice.
The workaround is to either exchange the public keys out of band, or distribute a certificate which can be used to verify public keys out of band.
Another potential security vulnerability in using asymmetric keys is the possibility of a man-in-the-middle attack, in which communication of public keys is intercepted by a third party and modified to provide different public keys instead. Encrypted messages and responses must also be intercepted, decrypted and re-encrypted by the attacker using the correct public keys for different communication segments in all instances to avoid suspicion. This attack may seem to be difficult to implement in practice, but it's not impossible when using insecure media (e.g. public networks such as the Internet or wireless communications). A malicious staff member at Alice or Bob's ISP might find it quite easy to carry out. In the earlier postal analogy, Alice would have to have a way to make sure that the lock on the returned packet really belongs to Bob before she removes her lock and sends the packet back. Otherwise the lock could have been put on the packet by a corrupt postal worker pretending to be Bob to Alice.
The workaround is to either exchange the public keys out of band, or distribute a certificate which can be used to verify public keys out of band.