Você está com sorte! Percona faz uma ferramenta chamada pt-online-schema-change
para exatamente esse tipo da situação.
pt-online-schema-change emulates the way that MySQL alters tables internally, but it works on a copy of the table you wish to alter. This means that the original table is not locked, and clients may continue to read and change data in it.
pt-online-schema-change works by creating an empty copy of the table to alter, modifying it as desired, and then copying rows from the original table into the new table. When the copy is complete, it moves away the original table and replaces it with the new one. By default, it also drops the original table.
Embora seja feito por Percona, ele funciona em qualquer uma das principais variantes do MySQL.