ALTER TABLE without locking the table?

Percona makes a tool called pt-online-schema-change that allows this to be done.

It essentially makes a copy of the table and modifies the new table. To keep the new table in sync with the original it uses triggers to update. This allows the original table to be accessed while the new table is prepared in the background.

This is similar to Dems suggested method above, but this does so in an automated fashion.

Some of their tools have a learning curve, namely connecting to the database, but once you have that down, they are great tools to have.

Ex:

pt-online-schema-change --alter "ADD COLUMN c1 INT" D=db,t=numbers_are_friends

This question from 2009. Now MySQL offers a solution:

Online DDL (Data Definition Language)

A feature that improves the performance, concurrency, and availability of InnoDB tables during DDL (primarily ALTER TABLE) operations. See Section 14.11, “InnoDB and Online DDL” for details.

The details vary according to the type of operation. In some cases, the table can be modified concurrently while the ALTER TABLE is in progress. The operation might be able to be performed without doing a table copy, or using a specially optimized type of table copy. Space usage is controlled by the innodb_online_alter_log_max_size configuration option.

It lets you adjust the balance between performance and concurrency during the DDL operation, by choosing whether to block access to the table entirely (LOCK=EXCLUSIVE clause), allow queries but not DML (LOCK=SHARED clause), or allow full query and DML access to the table (LOCK=NONE clause). When you omit the LOCK clause or specify LOCK=DEFAULT, MySQL allows as much concurrency as possible depending on the type of operation.

Performing changes in-place where possible, rather than creating a new copy of the table, avoids temporary increases in disk space usage and I/O overhead associated with copying the table and reconstructing secondary indexes.

see MySQL 5.6 Reference Manual -> InnoDB and Online DDL for more info.

It seems that online DDL also available in MariaDB

Alternatively you can use ALTER ONLINE TABLE to ensure that your ALTER TABLE does not block concurrent operations (takes no locks). It is equivalent to LOCK=NONE.

MariaDB KB about ALTER TABLE

The only other option is to do manually what many RDBMS systems do anyway...
- Create a new table

You can then copy the contents of the old table over a chunk at a time. Whilst always being cautious of any INSERT/UPDATE/DELETE on the source table. (Could be managed by a trigger. Although this would cause a slow down, it's not a lock...)

Once finished, change the name of the source table, then change the name of the new table. Preferably in a transaction.

Once finished, recompile any stored procedures, etc that use that table. The execution plans will likely no longer be valid.

EDIT:

Some comments have been made about this limitation being a bit poor. So I thought I'd put a new perspective on it to show why it's how it is...

• Adding a new field is like changing one field on every row.
• Field Locks would be much harder than Row locks, never mind table locks.
  
  
• You're actually changing the physical structure on the disk, every record moves.
• This really is like an UPDATE on the Whole table, but with more impact...