- Alter your user table to include a 'salt' column, default value of 'NULL'.
- Alter your login code to check if the user has a salt:
- If yes, compare the salted hashes and log in
- If no:
- Compare the unsalted hashes.
- Generate a random salt.
- Generate your salty hash.
- Store your new salt and hash in the database.
- Continue the login process.
Of course, you will also need to update your code for registration, password change/recovery, etc.
Alternatively, instead of a 'salt' column you could put in a 'hash_ver' column and use that to determine which validation method to use and when to update the hash. That way if you wish to use a hashing method that packs the salt in with the hash like bcrypt you don't get stuck trying to figure out what type of hash you're dealing with.