Creo que quieres esta sintaxis:
ALTER TABLE tb_TableName
add constraint cnt_Record_Status Default '' for Record_Status
Según algunos de sus comentarios, supongo que es posible que ya tenga null valores en su tabla que están causando que la alteración de la columna not null fallar Si ese es el caso, debe ejecutar una UPDATE primero. Su guión será:
update tb_TableName
set Record_Status = ''
where Record_Status is null
ALTER TABLE tb_TableName
ALTER COLUMN Record_Status VARCHAR(20) NOT NULL
ALTER TABLE tb_TableName
ADD CONSTRAINT DEF_Name DEFAULT '' FOR Record_Status
Consulte SQL Fiddle con demostración
