At one past employer, we used some tables substantially like the following:
The web app would switch out different algorithms based on which hash algorithm was being used. And if the hash used for a particular customer was now obsolete, they would be required to change their password, and it would update their row in the user table with the new hash. For some reason the business dudes (aka "suits") would change their minds about what was acceptable for hashing, and micromanage all sorts of things (for example, "salt must be prepended to the password", which was later changed to "no! salt must be added at the end of the password") based on whatever blog post or bizjournal they read that week. This lead to there being any number of hashing algorithms in use per year. I think that was horrible overkill, and there should only be 1 algorithm in use at any time (and at most 2 when switching from "old" to "new").
Salts were generally generated when the user signs up for the first one. But when the suits decided on a new hashing algorithm, they sometimes required that the salt get changed.
When EULAs would change, we'd have to force the user to read the new one and agree to the new one, and keep track of who agreed to what.
disclaimer: I used this picture on a different post.