Este é um direito doloroso, o comando alter leva anos para ser concluído. Para nossa sorte, existe uma ótima ferramenta da Percona que cuida disso (na maioria dos casos).
http://www.percona.com/doc/percona-toolkit/2.2/pt-online-schema-change.html
Esta ferramenta cria uma nova tabela e adiciona gatilhos à tabela antiga para atualizar a nova. Então, quando a cópia dos dados estiver concluída, as tabelas serão trocadas. Existem muitas opções para você modificar o comportamento. Aqui está um exemplo:
./pt-online-schema-change --alter "ADD INDEX ( project_id , user_id ), DROP INDEX project_name" D=MyGreatDB,t=project --user my_user --ask-pass --no-drop-old-table --no-check-replication-filters --max-lag 10 --dry-runAltere –dry-run para –execute quando desejar realmente iniciar a conversão