Hash Migration Strategies

I've had several engineers ask me recently about how to migrate very large number of users from an old non-salted md5 hash to SHA-512.

I can think of 2 main strategies:

1) Rolling migration: Weaker security, stronger user experience.
a) Add a new database column to your USER table that will hold the 1024 bits necessary for SHA-512.
b) Every time a user logs in, first check to see if the SHA-512 column is empty.
c) If empty, just verify the password though the old md5 hash. If that login is successful, rehash to SHA-512 and delete the md5 column.
d) If the md5 column is not empty, verify the password via SHA-512 (preferably with per-user salts and multiple iterations of the hash)

2) Mass migration: Stronger Security, weaker user experience.
a) Email users (in blocks of 10,000) that their password will be expiring soon.
b) At login time, do the same as a rolling migration except also force the user to change their password upon successful login.
c) If a user does not change their password within a limited amount of time, lock their account and force a customer service interaction in order to re-open the account - giving that user 1 hour to change their password or be locked out again.