If all rows are going to receive the same non-NULL value for this new column, then you can add the non-NULL column with a default constraint:
alter table T add NewColumn int not null constraint DF_T_NewColumn DEFAULT 1
It's then up to you whether you wish to leave this default constraint in place or to remove it now that the column has been populated:
alter table T drop constraint DF_T_NewColumn
The alternative (presented in your answer) may be more appropriate if you want to compute different values for each row, but you should be aware that it will have to scan the entire table at least twice during your 3 steps - once to set the new values and then again in order to verify that they're all non-NULL when changing the nullability of the column.