The situation we were discussing is not analogous to the SSH situation you describe because the key, namely hash(password), is not secret (the attacker knowing it was the premise of the scenario). It doesn't matter what mumbo-jumbo (not an insult, just an illustrative phrasing) you require the client to do, an attacker can do it just as well. The system is still vulnerable to attacks (which are not exactly replay attacks by the strict definition, but are still trivially equivalent) because it depends upon the key being secret, which is not the case.
Hashing on the client does not satisfy the first goal and sending the password in plaintext does not satisfy the second goal. A different solution altogether would be necessary to satisfy both goals.
I'm still confused. With my proposed system, how do you perform a replay attack (or the trivial equivalent thereof) without access to the server's database?
There are two scenarios here, and I think we are each discussing a different one.
The first scenario is where the attacker obtained the hash from the wire which is what I think you're assuming to be the case. Then yes, double hashing would protect against replay attacks.
The second scenario is where the attacker obtained the hash from the database which is what I assumed to be the case. Double hashing would not protect against these attacks (which are not, strictly speaking, replay attacks).
I'm not interested in belaboring this point any further, because I think you came up with a better solution to both issues in another post[1].
When the attacker obtains the hash from the database, this does indeed let him carry out the rough equivalent of a reply attack, but it doesn't let him carry it out on any other site. The reason you don't want passwords stored (or transmitted) in plaintext is so that an attack doesn't compromise the user's accounts everywhere. This double hashing scheme avoids that, but yes, leaves your account on this one site compromised if the database is copied.
Glad you liked the other scheme. It's more complex, but seems better. I really have to try it out at some point.
Hashing on the client does not satisfy the first goal and sending the password in plaintext does not satisfy the second goal. A different solution altogether would be necessary to satisfy both goals.