First of all - regardless of the advice you get, test your scenario on a test box. Restore the production database and test it out, without having to throw up out of nervousity :)
Anyway: Add the column as a NULL-able column will have considerably less impact than adding a column which must have an initial value. If you need an initial value, add it first as NULLable, update the existing rows (in batches) and then change to column to NOT NULL. Add a default value for the column already initially, so that new rows get the default value instead of being NULL. That way you can change to NOT NULL later on, when you have updated all rows with a value for the new column.
answered Mar 13 at 07:22 PM