Merkle's initial scheme for "Secure Communication over Insecure Channels," the first approximation of public key cryptography, could solve exactly this problem without even the need for the initial secure exchange of information.
Here is how Bruce Schneier summarized the scheme in his book "Applied Cryptography":
Merkle's technique was based on “puzzles” that were easier to solve for the sender and receiver than for an eavesdropper. Here's how Alice sends an encrypted message to Bob without first having to exchange a key with him.
- Bob generates 2^20, or about a million, messages of the form: “This is puzzle number x. This is the secret key number y,” where x is a random number and y is a random secret key. Both x and y are different for each message. Using a symmetric algorithm, he encrypts each message with a different 20-bit key and sends them all to Alice.
- Alice chooses one message at random and performs a brute-force attack to recover the plaintext. This is a large, but not impossible, amount of work.
- Alice encrypts her secret message with the key she recovered and some symmetric algorithm, and sends it to Bob along with x.
- Bob knows which secret key y he encrypts in message x, so he can decrypt the message.