There are many different ways to solve this, the easiest I can come up with right now is to use some kind of challenge; the server sends a value the client has to use as a salt. The server ensures that the value is unique, hasn't expired, and only used once (this makes sure a replay attack isn't possible.)
This makes sure that a plain text password isn't sent, only a hashed one. The server can trust (trust as much as when doing plain text auth anyway) the client to not simply resend some old hash since the clear text password is needed to compute the hash with the "one-time-salt".
Another, more sophisticated (and secure) way is to generate a RSA-keypair from the password where the server has the public key, and the client the private. The client also has a copy of the servers public key. The user enters the password, and only the correct password will get the correct rsa-key.
The user then encrypts the requests with the server's public key, and then signs the requests with the user's private key. Only the server can then decrypt the requests, and the server can verify that the sender really is the right user by verifying the sign with the user's public key. And the opposite for the response. To add some security you should add some unique "salt" as I wrote earlier to ensure replay attacks are impossible.