Table is locked while DDL queries are performed. This doesn't mean that the server doesn't accept queries on other sessions while locked but they are queued up and probably time out before your ALTER TABLE is done. Depending on factors like hardware, table structure and of course amount of rows (which you said is quite high) the alter will take a while.
On MySQL 5.5 (faster index creation, innodb), 8-core CPU, chip disks, altering a 5 mil row table with several indexes takes about 15-20 minutes in our case.
I suggest to create a copy, and alter the copy. You'll have to replay the data delta after you're done. Facebook had to deal with this on a way higher level, check this out
http://m.facebook.com/note.php?note_id=430801045932
Tho, I can't promise this would all work safely on the MyISAM Engine
EDIT:
Percona created a toolkit which apparently works on all storage engines:
http://www.mysqlperformanceblog.com/2012/04/05/percona-toolkit-2-1-with-new-online-schema-change-tool/
With this release we introduce a new version of
pt-online-schema-change, a tool that enables
you to ALTER large tables with no blocking or
downtime. As you know, MySQL locks tables
for most ALTER operations, but pt-online-
schema-change performs the ALTER without
any locking. Client applications can continue
reading and writing the table with no interruption.