How do I add a column to a table in SQL Server that doesn’t allow nulls?

You could add the column and provide the default value to be used for all existing rows.

ALTER TABLE foo 
ADD bar bit 
DEFAULT 0 NOT NULL;