How to add column to big table in MySQL
Use MySQL Workbench. You can right-click a table and select "Send to SQL Editor" --> "Create Statement". This way no table "properties" will be forgotten to add (including CHARSET or COLLATE).
With this huge amount of data I'd recommend cleaning up either the table or the data structure you use (a good DBA comes handy). If not possible:


rename the table (ALTER) and create a new one with the CREATE script you get from Workbench. You can also extend that query with the new field you need
BULK LOAD the data from the old table to the new one:
SET FOREIGN_KEY_CHECKS = 0;
SET UNIQUE_CHECKS = 0;
SET AUTOCOMMIT = 0;
INSERT INTO new_table (fieldA, fieldB, fieldC, ..., fieldN)
   SELECT fieldA, fieldB, fieldC, ..., fieldN
   FROM old_table
SET UNIQUE_CHECKS = 1;
SET FOREIGN_KEY_CHECKS = 1;
COMMIT;

This way you avoid indexing/etc to run record by record. The "update" to the table still will be slow (as the amount of data is huge) but this is the fastest way I can think of.
EDIT: Read this article to get details about the commands used in the above sample query ;)