Comment by pek

Couldn't you just move from, say, using MD5(password) to bcrypt(MD5(password))? So when it becomes apparent that the old hash is no more secure, start using the combination of the old bad hash (MD5) and the new good hash (bcrypt). This way you can simply run once through the password database, hash each password hash there with the new better hash, and throw away the old hashes. No need to prolong the process until the users log in.