Yikes, 15 year old software? That sounds rough. If the service can't be interrupted, I've seen the staged release work well:
Step 2 is the hardest because there's a lot of options of how you can handle this. I've personally had my software write to 2 different places, ran a migration to move the old data to the new place, and then updated the service again to only read/write from the new place.
Hopefully you're sourcing see good ideas from the communuty suggestions, these have all been good ideas if they solve your problem effectively.
I also can't stress enough the importance of DB backups, testing that your theory of deploys works at every step in a non production environment, and having your plan written down and reviewed by your peers. DB alters in prod are hard, and carry a lot of risk if something unexpected happens.
We're a place where coders share, stay up-to-date and grow their careers.
We strive for transparency and don't collect excess data.