If we look at a related topic, namely interactive identification protocols, we get a problem that has been well-studied.
Unfortunately there are no known protocols that are both secure (against attacks by computers) yet where ordinary humans can reasonably execute the protocol mentally without the aid of the computer. There have been lots of proposals, but all of them have either been broken or have proven too complicated for ordinary people to follow without making mistakes.
I think many researchers in the security and cryptography community expect that the problem is very hard and that, in all likelihood, no such secure and usable identification protocol exists. Of course, there is no proof of this -- it is not even clear how you could prove it, since it is not clear how you would formalize "can reasonably be executed by an ordinary human, in everyday life, without aid of a computer".
For a good entrance into the broad literature on interactive identification protocols, the following paper is excellent:
There's also the seminal paper by Hopper and Blum that motivated a lot of the work in this area:
Reading these two papers will give you a good sense of the directions, and a lot of relevant techniques and ideas. It will also help you understand why the interactive identification problem is so incredibly hard to do securely, without a computer.
Public-key cryptography is a strictly harder problem than interactive identification. If you could do public-key cryptography, you could also do interactive identification securely. For instance, I could prove my identity by demonstrating the ability to sign a random challenge chosen by the verifier; or by demonstrating the ability to decrypt a ciphertext chosen by the verifier. Therefore, my expectation is that there is no way to implement public-key cryptography securely without a computer, either.