Deploy code that understands both the new and old schema. Deploy the data migration code at the same time. After the deploy is successful, run the data migration code. It can be started manually, or automatically as part of your deploy script. When the migration is complete, manually remove the code that understands old schema, then deploy again.
