Updating a very large table

Hello people,

I have a large table to do update (in every tuple), the table (table1) has
about 8 millions tuples, and I had to add a new column (new_column).
The table1 is one of the most accessed table in my cluster, so I can't do a
direct update 'cause almost everyone stays in waiting.
Doing the update at night was unsuccesful, in the morning it was running
yet, and we had to kill it.

So, my question is, what the best practice, best way, (how do you handles
with a situation like this) for updating a very large table, every tuples in
a new column?

P.S.: Some people may thing that I have a Design Problem level, but don't,
new_column have to belong to table1, in this especific case.

Thks for response,

Rafael Domiciano