Adding columns & index to a huge table
First of all, use one alter statement to do all of adding two columns and the compound index. ALTER TABLE table1 ADD col1 INT, ADD col2 CHAR(2), ADD INDEX (col1, col5);. More about ALTER
Archiving old records is a good idea. If it is very rarely needed, then some slowness is affordable (I think).
Depending on your engine that you use, dumping the data and importing it to a new table maybe slow if you can't disable the keys. If you drop all indexes and recreate them, that is slow again. If you can afford some down time, any method is ok.
If the tables keeps growing, and you don't want to archive, you may consider "Sharding" the table, but that would require some extra efforts at development level
Last idea, which I don't strongly recommend unless you can't afford downtime, is to create a new table with a primary key and the new column that you want to add. Use this PK to join the original table.