When you can't take downtime, the “trick” to data migration is: Think small changes.
- New table
- Update writes to go to old and new
- Background job to migrate old data to new
- Move reads to new table
- Stop writing to old table
Each of these steps is a deploy.