La prima cosa che mi viene in mente è quella di fare il backup in modo classico.
Una volta ripristinato il db giocare con l'information_schema in modo da generare dinamicamente tutte le query per l'aggiunta delle due colonne.
codice:
select concat("alter table ", table_name, " add column col1 varchar(50) default 'valore1' first; alter table ",table_name," add column col2 varchar (50) default 'valore2' after col1;")
from information_schema.tables
where table_schema = 'nome_database' and table_type = 'base table'
A questo punto esegui tutte le query generate.
Lo script ovviamente presuppone che i due valori siano uguali in tutte le tabelle.