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).
This looks interesting. Do you know how it actually works? The readme simply says, "The basic idea is to perform the migration online while the system is live, without locking the table. In contrast to OAK and the facebook tool, we only use a copy table and triggers." What's the technique used to achieve that?
From what I understand, it creates a new table with the same structure as the existing table, runs your migrations on it, adds triggers to bring live changes in from the original table while copying (in batches) the records in the old table. Once everything is copied and updated with triggers, it swaps out the old table for the new one in an atomic operation.
[1] https://github.com/soundcloud/lhm