- Add a new salt column, initially null.
- When an authentication request comes in, check the salt field.
- If the field has a value then this is a new-style hash that has pepper and salt added. Handle accordingly.
- If not, then this is an old-style hash. Verify using the old mechanism. Assuming it succeeds, you now have the plaintext password from the original request; generate and store a salt and you now have everything needed to compute a new-style hash and can replace the old one.
Eventually either everyone has logged in at least once and had their hashes transparently updated (there are no NULL salts left in the table), or the only ones left are the ones who never use the system anyway and wouldn't notice being locked out. Either way, the old-style hash support and transitional code can be removed (e.g., declaring the salt field NOT NULL).