¿Cómo puedo agregar una columna que no permita valores nulos en una base de datos de Postgresql?

Tienes que establecer un valor predeterminado.

ALTER TABLE mytable ADD COLUMN mycolumn character varying(50) NOT NULL DEFAULT 'foo';

... some work (set real values as you want)...

ALTER TABLE mytable ALTER COLUMN mycolumn DROP DEFAULT;