Radek's solution looks great. I would add a comment if I had the reputation for it, but I just want to mention that if you are doing this you'll likely want to widen the sequence for the primary key as well.
ALTER SEQUENCE my_table_id_seq AS bigint;
If you just widen the column type, you'll still end up with problems when you hit 2 billion records if the sequence is still integer sized.
I think the issue that James points out about adding the primary key requiring a table scan can be solved with the NOT VALID/VALIDATE dance. Instead of doing alter table my_table add constraint my_table_pk primary key using index my_table_pk_idx;
, you can do
ALTER TABLE my_table ADD UNIQUE USING INDEX my_table_pk_idx;
ALTER TABLE my_table ADD CONSTRAINT my_table_id_not_null CHECK (id IS NOT NULL) NOT VALID;
ALTER TABLE my_table VALIDATE CONSTRAINT my_table_id_not_null;
I think it's also worth mentioning that
create unique index my_table_pk_idx on my_table(new_id);
will do a full table scan with an exclusive lock on my_table. It is better to do
CREATE UNIQUE INDEX CONCURRENTLY ON my_table(new_id);