I've been doing more testing on several different machines, but still haven't found a solution to my problem where VACUUM FULL is running out of memory. Besides the original case on RHEL4, I've been able to reproduce it on both Windows and OSX, with 3GB and 5GB RAM, respectively. Interestingly, it always fails on a request size of 330, even across differently-sized databases running on machines with different amounts of memory.
As far as that new tool you're describing, for my purposes it doesn't make much difference whether it's a stand-alone application or a command, though a command is a little more convenient. The ability to free space concurrent with other database operations would be nice, but I feel like the introduction of serialization failures would negate that advantage, since I at least would end up running it non-concurrently to avoid dealing with them.
I actually find the current design of VACUUM FULL reasonable enough, if I could figure out what's causing this memory issue and prevent it from happening.
David