Так понимаю, вопрос не в "быстро", а в "без длительного простоя". Правильно?
Могу предложить:
Довольно просто и на коленке:
добавляете таблицу "need_update_rows", в которую триггерами на insert и update пишете первичный ключ записей, которые соответственно добавились и изменились. Достаточно того же самого первичного ключа (только без AI) и insert ignore
Когда удостоверились, что данные триггерами пишутся, создаете новую таблицу, какую хотите. Заполняете её insert select'ом, читая по первичному ключу диапазонами этак в пару сотен тысяч строк. Когда дописали основной объём - блокируете базу, дописываете и обновляете строки из need_update_rows, делаете RENAME TABLE (он делается очень быстро независимо от размера таблиц), снимаете блокировку с базы.
Другой вариант:
поднять реплику. Mysql умеет реплицировать в другой storage engine.
С такой табличкой не забудьте сделать партицирование. Пригодится.