Disk is full after a PostgreSQL operation. Now what?

I added a column to a huge table in PostgreSQL. Since the table occupied more than 50% of the free disk space and the operation was running in a transaction, all of the disk space got consumed by the edited rows before the transaction could finish and the operation failed. Now I know how I should do it properly – add the columns and then add their values in batches, but every time I try now, the DB runs out of disk space after a couple of batches, even if I run VACUUM ANALYZE between the batches.

In the past, I would run VACUUM FULL and get the free space back. However, since version 9.0, the VACUUM FULL command works similarly to the CLUSTER command and requires some free disk space to finish, which I don’t have.

Is there a way to clean up the DB in-place and reclaim the free space?