I've had to solve this same issue twice before:
- My first web app, I actually knew enough to MD5 hash users' passwords; I did not, however, know about salt, and worked that in later.
- Actually the same web app, a few years later, when I decided to "upgrade" to SHA-512 from the existing MD5.
In both cases, I used neither of your options, but rather option 3: Upon a user's next login, use the password to generate the new hash and replace the old one (after verifying against the old one).
In the case of adding a salt, this was pretty trivial: All I did was default everyone to a salt of "" (empty string), which could be concatenated and then hashed without having any effect whatsoever on the resultant hash; once authenticated, I generated a new salt for the user and then re-hashed the password, saving that new result.
Upgrading from MD5 to SHA-512 was a tad trickier, but by simply looking at the string length of the has in the table (I didn't use a new column for the new hash, merely expanded the existing one to accommodate the longer hash) I could tell which algorithm to use and then authenticate the user appropriately; once authenticated, if they were still on the old hash I would compute a new one (also taking the opportunity to generate a brand new salt) and store that.
In both cases I of course did eventually run into the situation where further down the road "old style" passwords still existed. After waiting an appropriate amount of time (e.g. 6 months), simply decide that those that haven't logged in since the new style was adopted are "inactive": Generate and store a new, completely random password for them (using the new style of storing it, of course), and if they ever did come back they would have to use your password reset mechanism to regain access. (Alternatively, leave as-is, but effectively invalidate it by simply dropping the code for the old style.) You could (if applicable) also send an e-mail to these users, asking them to log in to complete a security upgrade on their account, before invalidating their current password.
This approach does involve additional code in the authentication routine, of course, but it's only temporary -- once everyone has upgraded (whether by logging in or by being "forced" in as in the previous paragraph), you can remove all code responsible for performing the upgrade. Security upgrade complete, with the majority of your users (and all of your regular users) having never noticed a thing!