In the book "High Performance MySQL" Second Edition by Jeremy Zawodny & Peter Ziestev there is a high-speed, high-risk method of adding a column to table, regardless of table size. It goes something like this:
METHOD 1
Assuming db is the database where xxx resides
Step 1. CREATE TABLE zzz LIKE xxx;
Step 2. ALTER TABLE zzz add yyy smallint default NULL; -- Not using 0 for now
Step 3. Perform the following in the OS
service mysql stop
cd /var/lib/mysql/db
mv xxx.frm xxxold.frm
cp zzz.frm xxx.frm
service mysql start
Step 4. Try and see if xxx is accesible
If this does not work try this:
METHOD 2
Step 1. CREATE TABLE zzz LIKE xxx;
Step 2. ALTER TABLE zzz add yyy smallint default 0;
Step 3. INSERT INTO zzz (col1,col2,...colN) SELECT col1,col2,...colN FROM xxx;
Step 4. ALTER TABLE xxx RENAME jjj;
Step 5. ALTER TABLE zzz RENAME xxx;
The second method has to work. The first is recommended from that book I mentioned.
Give them a Try !!!
P.S. before trying the first method, backup everything (LVM snapshot)