Most efficient way to add a serial column to a huge table
What's wrong with:
ALTER TABLE foo ADD column bar bigserial;

Will be filled with unique values automatically (starting with 1).
If you want a number for every existing row, every row in the table has to be updated. Or do you not?
The table will be bloated to twice it's size if it cannot reuse dead tuples or free space on the data pages. Performance of the operation might benefit a lot from a FILLFACTOR lower than 100 or just random dead tuples spread out over the table. Else you may want to run VACUUM FULL ANALYZE afterwards to recover disk space. This won't be quick, though.
pgstattuple
You may be interested in this extension. It helps you gather statistics on your tables. To find out about dead tuples and free space:
Install extension once per databae:
CREATE EXTENSION pgstattuple;

Call:
SELECT * FROM pgstattuple('tbl');


Alternative
If you can afford to create a new table, which would break depending views, foreign keys, ...
Create an empty copy of the old table:
CREATE new_tbl AS
SELECT *
FROM   old_tbl
LIMIT  0;

Add the bigserial column:
ALTER new_tbl ADD column bar bigserial;

INSERT data from old table, automatically filling the bigserial:
INSERT INTO new_tbl
SELECT *    --  new column will be filled with default
FROM   old_tbl
ORDER  BY something; -- or don't order if you don't care: faster

The new bigserial column is missing in the SELECT of the INSERT and will be filled with its default value automatically. You can spell out all columns and add nextval() to the SELECT list to the same effect.
Make sure you got all your data in the new table.
Add indexes, constraints, triggers you had in the old table now.
DROP TABLE old_tbl;
ALTER TABLE new_tbl RENAME TO old_tbl;

Might be quite a bit faster overall. This leaves you with a vanilla table (and indexes) without any bloat.
You need free disk space - around the size of the old table, depending on the state of the table - as wiggle room. But you may need just as much with the first simple method because of table bloat. Again, the details depend on the state of your table.