So your site uses terrible password hashing scheme H1 (perhaps MD5), and you want to migrate to secure password hashing scheme H2 (preferably scrypt, but possibly bcrypt or PBKDF2).
The standard migration approach is to upgrade users as they log in and enter their password. There are insecurities and workarounds doing this, but there's an alternative that instantly secures everybody using your service with no distruption:
Change your password hash to H2(H1(password)).
- Can be done immediately for everyone, because you know H1(password).
- Critical parameters such as salt, CPU-hardness (stretching), and possibly memory-hardness (scrypt FTW) are provided by H2.
- Weaknesses in H1, such as collisions, don't affect the limited use case of password hashing.
I first heard of this idea from Avner Rosenan, and there's an interesting discussion about it on crypto.stackexchange.com.