How do you update password storage if you don't store the passwords only hashes?

You could upgrade it for new users, but for old ones? (e.g. I don't change passwords often)

When a user whose password is hashed the old way logs in, after checking the password they just supplied against your stored old hash but before forgetting the plaintext, you can compute the new hash & update your records.

Of course, that only works for active users - it won't upgrade anyone that never logs in. Depending on just how weak the old hash is, you may want to eventually cut off any lingering un-upgraded accounts: just forget their old hash, requiring them to go through your password reset process should they ever come back. If you've left it long enough, those accounts will probably never be used again anyway, so that should be NBD.

I updated a DB from MD5 to BCrypt at my last job. Essentially on the next login I updated the password (since the password isn't hashed on the client end). So all active users got switched over. After a relatively short period I reset the remaining passwords and forced users to send password reset emails to login.

Onion hash: hash the existing hash with the new algorithm.

That throws away entropy, but I suppose so long as very few hash collisions of a password are likely to be real passwords themselves it would be harmless.

You could rehash the password the next time the user logs in.

You ask people to change their passwords, and when they do so, you store them with the new scheme. You can do that by e.g. requiring everyone to change their password on their next login/visit.

You don't even need to ask people to change their passwords; when they login, you have a copy of the original password, so you can just store the new hash over the old.

If they aren't salted, just generate your own rainbow table!