Awesome writeup! Validating to see that the way I do it is the way stripe does it with bajillions of records, while the system is running. Very pragmatic and incremental - maybe a little overly cautious with the feature flag, but better safe than sorry.

I've had to do similar when migrating password schemes. When users login they would validate against their current password, and then generate a new password hash to use next login. Although these types of migrations usually take quite a while, as a user has to login for the migration to happen.