¿Puedo agregar una columna no nula sin valor DEFAULT?

No, no puedes.

Porque si pudiera, SQL no sabría qué poner como valor en los registros ya existentes. Si no tuviera ningún registro en la tabla, funcionaría sin problemas.

La forma más sencilla de hacer esto es crear la columna con un valor predeterminado y luego eliminar el valor predeterminado.

ALTER TABLE dbo.MyTable ADD
MyColumn text NOT NULL CONSTRAINT DF_MyTable_MyColumn DEFAULT 'defaultValue'
ALTER TABLE dbo.MyTable
DROP CONSTRAINT DF_MyTable_MyColumn

Otra alternativa sería agregar la columna sin la restricción, llenar los valores de todas las celdas y agregar la restricción.