How to insert a new column in a huge MYSQL Database Table?

If it's production:

You should use pt-online-schema-change of Percona Toolkit.

pt-online-schema-change emulates the way that MySQL alters tables internally, but it works on a copy of the table you wish to alter. This means that the original table is not locked, and clients may continue to read and change data in it.

pt-online-schema-change works by creating an empty copy of the table to alter, modifying it as desired, and then copying rows from the original table into the new table. When the copy is complete, it moves away the original table and replaces it with the new one. By default, it also drops the original table.

Or oak-online-alter-table which is part of openark kit

oak-online-alter-table allows for non blocking ALTER TABLE operations, table rebuilds and creating a table's ghost.

Altering tables will be slower, but it doesn't lock tables.

If it's not production and downtime is okay, try this approach:

CREATE TABLE contacts_tmp LIKE contacts;ALTER TABLE contacts_tmp ADD COLUMN ADD processed INT UNSIGNED NOT NULL;INSERT INTO contacts_tmp (contact_table_fields) SELECT * FROM contacts;RENAME TABLE contacts_tmp TO contacts, contacts TO contacts_old;DROP TABLE contacts_old;