I think asymmetric encryption would solve all problems. The sever only ever stores the users public key and uses challenge-response to prevent replay attacks.
This is a bad idea, but if you are required that your uses have passwords, you could use their password to seed an elliptic curve private key to create the user key on the fly.
So you go to a site, you enter your password, but then javascript creates a private key and public key based on the userid and password (which is a unique tuple). The key will always be the same regardless of the password.
When you first set your password, it sends the public key to the server, which is then stored. If that key was intercepted, it's not a problem.
Then the server challenges by sending a random code, which the client uses the private key to encode, sends back, the server then decodes with the public key. That guarantees that the private key is known by the client, and thus the password is known, but the private key never leaves the machine.
The second time you go to the site, you get the challenge, and respond. Neither private nor public key is transferred.
I don't think there's a solution that "solves all problems". What if you want to log in using a dumb terminal or not execute untrusted code on your host?
This is a bad idea, but if you are required that your uses have passwords, you could use their password to seed an elliptic curve private key to create the user key on the fly.