We always did that in batches about 1k to 10k rows. Takes a while but at least doesn't hammer the DB.
The following query will show dead tuple count for the table: select tuple_count, dead_tuple_count from pgstattuple('table_name');
create a temporary index covering that column. Then it will be in the range of ms.
With this the re-check for nulls when adding the not null constraint will not take any time at all.