Q:

Authentication with an untrusted server

I asked a related question earlier, but I want to ask a broader version this time:
To simplify things let's say I've developed an application that allows users to send messages in a chat room, and to each other (similar to IRC). The nature of the message doesn't require too much secrecy, nothing sensitive is ever shared.
I develop an open-source server and an open-source client for the application. Users will setup their own servers, I simply provide the server and client programs.
I want users to have accounts on each server. The client should ideally log on with a username and a password.
I can assume the client won't steal account information because the user got it from a trusted source. The problem is the server can't be trusted because:

Each server's owner can make modifications to their server's code. 
They can see the contents of any database. 

How can I authenticate users:

without letting the server owner access the user's password
without letting the server owner access a precursor to a user's password (anything that isn't the password, but can either be turned into the users password, or used to log into another server).
without relying on an precomputed key that has to stay hidden on either the client or server (the source code would reveal it).
ideally allowing a password
Edit: Ideally the password and username would be all it'd take to log on, so logging on with different machines the user would only need the password and username.

The approaches I have in mind:

Challenge-Response: Send a challenge, hash it with a password, and send it as a response. This passes requirement numbers 1 and 3, but fails the 2nd, as it requires the server to also have access to the hashed password, which can be turned into the actual password, or used to log onto other servers (the latter is slightly lesser, since it can be dealt with if it occurs). My other question goes into details on how I implemented this idea for testing.
2: Server Whitelist: This feels a little like cheating, but it meets all the requirements by "removing" the biggest issue, the fact the server can't be trusted. If the client tries to connect to a server not on the whitelist, a strongly worded warning would be issued(or access to non whitelisted servers could be completely blocked). This has the downside of complicating the process of users creating new servers, and it places more responsibility on me than simply developing the application (I'd have to manage the whitelist). It also doesn't necessarily ensure that the server can be trusted since even if the owner isn't malicious, there's no guarantee they have proper security on their systems.

A:

Any solution is going to involve some public key cryptography. Each user can have a key pair. The secret key could be encrypted with a password as suggested by @Mark.
If it is for some reason not practical to store a private key, and the user must be able to log in using just the software and a password, the private key can be generated on the fly.
You can have a database containing the following for each user:

User data
A salt for the user's password
A salt for the public key
A hash of the public key (Made with the above salt)

To authenticate:

The password salt is sent to the client. 
The client combines the password salt and the password and use this combination to seed a PRNG. 
The output from the PRNG is used as input for any private key generation algorithm you choose (RSA or any other signature algorithm). 
The public key is then sent from the client to the server. 
The client must also prove that it holds the corresponding private key (this could be done by signing a session identification or through a sigma protocol).
Once the server knows that the client has the secret key, it validates the public key by hashing the public key with the stored salt and compares the result to the hash stored in the database.

The order of the last two steps was chosen to prevent an attacker who somehow learned public key (but not private key) from learning if that public key could be used to access a particular account.
No iterated hash is needed, as the algorithm to generate the key pair tend to be sufficiently computationally intensive. Unlike the iterated hash, the key pair computation does serve the secondary purpose of keeping the secret information well hidden from the server.
If the existence of a user account must be concealed, the server can simulate the protocol when a non-existing username is provided as follows:

In the first step of authentication generate a pseudorandom password salt and send this to the client.
Follow the protocol through all the following steps not depending on the database.
In the last step of authentication compute a hash and discard the result. Reject the user regardless of the value of the hash.

The remaining challenge in concealing the existence of a user account is how to produce a psuedorandom password that changes at a frequency, which is indistinguishable from the frequency of password changes for a real user.

