Not that im excusing mysql, but what I do when adding columns to a +10mil row tables is to create a new table with the new column and then insert into newtable from oldtable.

That changes those few hours into few seconds.