btrfs ERROR: error during balancing - No space left on device

There are ways to get balance to run in this situation.

sudo btrfs fi show
sudo btrfs fi df /mount/point
sudo btrfs fi balance start -dusage=10 /mount/point

If the balance command ends with "Done, had to relocate 0 out of XX chunks", then you need to increase the "dusage" percentage parameter till at least one chunk is relocated.

if the balance command fails with:

ERROR: error during balancing '/blah/blah/blah' - No space left on device

You might actually need to delete files from the device to make some room. Then run the balance command again.

However, thanks to Marc's Blog: btrfs - Fixing Btrfs Filesystem Full Problems here is another option:

One trick to get around this is to add a device (even a USB key will do) to your btrfs filesystem. This should allow balance to start, and then you can remove the device with btrfs device delete when the balance is finished. It's also been said on the list that kernel 3.14 can fix some balancing issues that older kernels can't, so give that a shot if your kernel is old.