Add column on huge InnoDB table in MySQL 4.1
You can use statement-based replication and add the column to a slave first.  Any pending modifications will queue up on the slave, and apply once the alter has complete.  When the slave is fully up to date with the new schema, you can effectively 'promote' it.

I am sure you are aware, but MySQL 4.1 is quite old.  Triggers were not introduced until MySQL 5.0 (2005), so this limits your options to use tools like pt-online-schema-change.