For ActiveRecord (or other Ruby-based) migrations with MySQL, I've had good luck with Large Hadron Migrator[1]. It's worked flawlessly for some of our own tables with several hundred million rows (and no downtime).
Create a new table, add triggers from old table to new table (with new column(s)), copy data, once everything is copied, switch the tables