Как быстро добавить новую колонку в большую таблицу (4млн+ строк)?
Обновитель до mysql 5.6. Там alter table появился уже неблокирующий: https://dev.mysql.com/doc/refman/5.6/en/innodb-onl...
4млн строк - это не много. Если конечно там не 100 столбцов и столько же индексов.
Движок таблицы то какой??
В любом случае с офлайном можно (наверное самый быстрый способ) это ваш вариант перечисленный в вопросе с одним отличием. Пунк 3 заменить на mysqldump с последующей корректировкой "шапки" дампа в соответствии с измененной структурой новой таблицы, дропнуть исходную и отресторить таблицу в новом виде (переименовывать ничего не надо). Из практики использования мускула на слабых серверах с ограниченными ресурсами могу сказать, что быстрее чем дамп - никакая другая процедура такие манипуляции не делает.