4. Expire all passwords and ask your users to come reset them. - No legacy code necessary
Regular users should have no problems if there's an accompanying blog post
Non-regular users might just remember about your site/service and come back :)
5. Use bcrypt/password stretching. Store the work value alongside the password and upgrade it as people log in.
To me that's not really keeping legacy code around; just an extra variable...
AFAIK its this
1. Continue using legacy, less secure hashing algorithm
2. Upgrade your password storage scheme and carry around some extra code and/or fields in your db.
3. Crack you own users passwords and convert them
Its all kind of smelly but 2 seems like the only option (unless I'm missing an option?)