insert a NOT NULL column to an existing table

As an option you can initially create Null-able column, then update your table column with valid not null values and finally ALTER column to set NOT NULL constraint:

ALTER TABLE MY_TABLE ADD STAGE INT NULL
GO
UPDATE MY_TABLE SET <a valid not null values for your column>
GO
ALTER TABLE MY_TABLE ALTER COLUMN STAGE INT NOT NULL
GO

Another option is to specify correct default value for your column:

ALTER TABLE MY_TABLE ADD STAGE INT NOT NULL DEFAULT '0'

UPD: Please note that answer above contains GO which is a must when you run this code on Microsoft SQL server. If you want to perform the same operation on Oracle or MySQL you need to use semicolon ; like that:

ALTER TABLE MY_TABLE ADD STAGE INT NULL;
UPDATE MY_TABLE SET <a valid not null values for your column>;
ALTER TABLE MY_TABLE ALTER COLUMN STAGE INT NOT NULL;

If you aren't allowing the column to be Null you need to provide a default to populate existing rows. e.g.

ALTER TABLE dbo.YourTbl ADD
    newcol int NOT NULL CONSTRAINT DF_YourTbl_newcol DEFAULT 0

On Enterprise Edition this is a metadata only change since 2012