Yup, add a new nullable column, update in small batches running log backups between the batches to prevent the log from blowing out (that's probably what used all the space).
Or create a new table, move the data over in chunks and delete the old table when done
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)SQL In The Wild
: Discussions on DB performance with occasional diversions into recoverability
We walk in the dark places no others will enter
We stand on the bridge and no one may pass