Combining some of the comments on the other answers, this was the solution that worked for me (MySQL 5.6):
create table mytablenew like mytable;  
alter table mytablenew add column col4a varchar(12) not null after col4; 
alter table mytablenew drop index index1, drop index index2,...drop index indexN; 
insert into mytablenew (col1,col2,...colN) select col1,col2,...colN from mytable;  
alter table mytablenew add index index1 (col1), add index index2 (col2),...add index indexN (colN); 
rename table mytable to mytableold, mytablenew to mytable 
On a 75M row table, dropping the indexes before the insert caused the query to complete in 24 minutes rather than 43 minutes.
Other answers/comments have insert into mytablenew (col1) select (col1) from mytable, but this results in ERROR 1241 (21000): Operand should contain 1 column(s) if you have the parenthesis in the select query.
Other answers/comments have insert into mytablenew select * from mytable;, but this results in ERROR 1136 (21S01): Column count doesn't match value count at row 1 if you've already added a column.