Alter table add column query blocking a table or taking so much time
The table will need to be physically rewritten on disc to include the extra column.   For this to happen the table has to be exclusively locked while this is happening.  If the applications running on this database are not shutdown then you may be waiting sometime before this exclusive lock on the table can be given.

Given you mentioned that this table has several million rows the alter table statement is going to take quite some time (this also depends how much data is stored in each record.  You will in all likelyhood need to stop all access to this table during this time (well it will be locked anyway).

Sorry if the answer is a little vague you did not really give many details about the size of the table and how much data is currently stored there.