How can I validate a hashed password if all I have is another hash? The Scenario
I have a client-side web application that bounces requests against a server-side API.  For the sake of simplicity, every request must pass a username and password.  This is similar to old school XML-RPC where the username and password are passed as parameters in every request.
However, as this is a REST service, some of the requests (GET and DELETE) don't have message bodies and must pass the username and password as query variables in the URL:
GET http://application.url/endpoint?username=xxxx&amp;password=xxxx

This is, frankly, a bad idea.  Requests are logged on the server, so if I send the password in plaintext, it's now sitting in a log file somewhere on the server.  I don't ever want to be sending the password in plaintext over the wire, so I'm stuck with a dilemma.
Approach 1
The first approach to solving this over-the-wire problem was proposed by a coworker:

Encrypt the password using something like Blowfish and store it in the database.
The client hashes the plaintext password plus some salt using some known scheme (i.e. SHA512).
The client send the hash and salt to the server.
The server decrypts the stored password, hashes it with the provided salt, and compares it to the provided hash.

This is an effective means of sending sensitive data across the wire (if the logs were read, no one would be able to snag the password).  But it breaks another one of my personal security rules - I have access to the user's original password!
If the password is stored in the database using reversible encryption, then it's still vulnerable to attack.  Someone could steal my database and decrypt the password.  To me, this is almost as bad as storing it in plaintext to begin with.
The server should not have access to the plain text password.
Approach 2
This approach was suggested in passing by a fellow developer and, on the surface, seems to solve some of my problems.

Hash the password with some salt and store the hash and salt in the database (no plaintext!).
The client encrypts the password using the server's known public RSA key
The client sends the ciphertext to the server.
The server decrypts the password using its private key and hashes the recovered plaintext with a known salt.
The server compares the computed hash with the hash stored in the database.

Once again, an effective way to prevent sending the plaintext password over the wire.  It has the added benefit of never storing the plaintext on the server as well.
But it still bugs me, because the server can see the plaintext after decryption.  Though I can build the system today to be secure, there's no guarantee another developer won't add logging somewhere in the future and write the plaintext to disk.
I'd be much happier if the server never had access to the plain text password.
End Goal
At the moment, approach #2 is the best solution I've come up with and will probably be what I end up implementing.  But there is an ideal solution out there ... I just don't know how practical (or even possible) it might be:

Hash the password with some salt and store both in the database (no plaintext!).
The client hashes the password on its end with its own salt.
The client sends the hash (and the salt?) to the server.
The server runs some other functionality to see if the two hashes (its and the client's) were generated by the same plaintext - it does not get the plaintext.

I could wire up some kind of challenge/response system (where the client asks for a salt, hashes the password with that salt, sends the response, and the server compares it with what it expected), but I'm trying to keep requests to a minimum.  So you'd only make one call to the server when you make the request rather than one call to authenticate and another to execute.
Is this last scenario even possible?
With the method below, the server never sees either the password or the key the password decrypts.

To generate a password:

The client generates a new RSA key, encrypts it with the password (using something like PBKDF2 to generate a symmetric key), and hands the server the RSA public key and the encrypted private key.

To Authenticate:

The server sends the client the encrypted RSA private key and a challenge. The client uses the password to decrypt the RSA private key and then signs the challenge. The client sends the signed challenge back to the server. The server verifies the signature with the RSA public key.

Caution:

Make sure changing passwords involves creating a new private key, not re-encrypting the old one with the new password.

--

This has an extra request. You can avoid that with two tricks:


Have the client store the encrypted private key so it doesn't need to ask the server for it.
Have the client store a sequence number to use as the challenge (or a timestamp and a random number), so it doesn't need to get a challenge from the server.