I think you need to separate in your mind confidentiality protection from authentication.
It is quite possible to simultaneous generate a key between two parties over the Internet, with everyone from your ISP to every Govt possible listening in, yet they cannot as an eavesdropper also generate that key. That is the essential point of say the Diffie–Hellman key exchange (https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange). But both parties can use that key for confidentiality protection ONLY; in that scenario neither party truly knows who they formed the key with.
The reason being, if all those baddies on the Internet are active man-in-the-middle, each party could wind up creating a key over-the-Internet with the man-in-the-middle, and be none the wiser. Hence a proper secure communication system includes authentication first, then confidentiality second. For authentication, indeed you need some means out-of-band to get the absolutely true identity key of the other party (and there are a lot of ways to do that with varying levels of reliability). But once you've established identify and authentication of your other party, it is possible to develop keys used for confidentiality purposes over the Internet (by also including the authentication keys in the key exchange process so the man-in-the-middle cannot hijack it).
Re WhatsApp, it gets its security from TextSecure, which relies upon the security of the Off-the-Record Messaging protocol. Start with the Wikipedia article; it has a subsection that discusses authentication of the two parties: https://en.wikipedia.org/wiki/Off-the-Record_Messaging