Você pode querer ver pt-online -schema-change do kit de ferramentas Percona. Basicamente o que ele faz é:

• Copia a estrutura original da tabela, executa ALTER.
• Copia linhas da tabela antiga para uma recém-criada.
• Usa acionadores para rastrear e sincronizar alterações durante a cópia.
• Quando tudo estiver concluído, ele troca as tabelas renomeando ambas.

Funciona muito bem para bancos de dados de instância única, mas pode ser bastante complicado se você usar replicação e não puder parar os escravos e reconstruí-los posteriormente.

Há também um bom webinar sobre isso aqui .

PS:Eu sei que é uma pergunta antiga, apenas respondendo no caso de alguém acessar isso via mecanismo de pesquisa.