It should be trivially easy to do the key exchange without WhatsApp being able to intercept the keys, even though they are relaying them between the two parties.*
Assume Alice and Bob both use WhatsApp. Each generates a certificate with a private and public key. They publish their public keys via some directory service. Alice wants to chat to Bob securely. They currently don't have a relationship set up between them. So Alice looks up Bob's public key, and generates a random encryption key to be used for chatting with Bob. She encrypts this key with Bob's public key and sends this encrypted key to Bob over WhatsApp. Only Bob can decrypt this because only Bob has the private key - WhatsApp doesn't. Bob can either then use the same key to send messages to Alice, or he can repeat the process, so that even if one key is exposed somehow, only one half of the conversation can be decrypted.
Yes, WhatsApp's app must ultimately be trusted to be storing the private keys securely and not leaking them back to WhatsApp somehow, but if they're going to the trouble of implementing end-to-end encryption, then entire point is that they want to be able to simply auto-respond to any law enforcement requests with 'We simply cannot decrypt the messages even if we want to." Given that WhatsApp already has been encrypting messages between client and server for some time now before this, it doesn't make sense for them to implement such an elaborate encryption scheme and then leave a backdoor in it, which will inevitably be discovered, either by a security researcher or when they give in to a law enforcement request.
* I haven't actually read up on how WhatsApp is doing their key exchange, so they may be doing exactly this.