I'm sure you have all read http://bazaar.launchpad.net/~mysqlatfacebook/mysqlatfacebook/tools/annotate/head:/osc/OnlineSchemaChange.php already, but if you haven't, it might be neat to look at evaluating and possibly integrating it into MariaDB.