I realize something like this would be the holy grail of communications security and have never heard anything to suggest it has been done.

Am just wondering. A lot of mathematicians and computer scientists spend time doing proofs for theoretical situations. Has anyone done a proof to rule out the possibility of ever doing a key-exchange (or some other encryption setup) over an open or already compromised line?

To be clear I mean : A and B are communicating while C has the potential to be listening (ideally C is not listening in real time and is only logging A&B for action later). Is it impossible for A and B to ever exchange information over the compromised line to setup a new encrypted line that C can't immediately crack?

Last Clarification : I'm realizing public key may technically satisfy the problem by not transferring the whole method of encryption over the line. Is there anything else you do, even if only theoretical? This feels like more of a loophole than directly solving things.

If the attacker is only passively listening to the connection then Diffie Hellman Key Exchange can be done to create a common key known only to the communication peers.

But, if the attacker can not only listen to the connection but also actively modify the transferred data, then the attacker might mount a man-in-the-middle attack and claim to be the expected communication partner for both A and B. This can only be prevented if  A can identify B before starting the encrypted communication and thus knows that it exchanged the key with the expected partner. For this it needs a secure way to verify the identity even if the line is compromised. This can be done by public-key cryptography. But of of course it needs some kind of prior knowledge about the expected identity of B, i.e. either A knows B already (direct trust) or it knows somebody who knows B etc (trust chain). 

You'll find an implementation for all of this with SSL/TLS and the associated PKI. This is used with https in the browsers and the necessary trust anchors for building the trust chain are the public certificate agencies which are either known by the operating system or by the browser. For more information see How does SSL/TLS work?.
