"no space left on device" even after removing all containers

The problem is that /var/lib/docker is on the / filesystem, which is running out of inodes. You can check this by running df -i /var/lib/docker

Since /home's filesystem has sufficient inodes and disk space, moving Docker's working directory there there should get it going again.

(Note that the this assumes there is nothing valuable in the current Docker install.)

First stop the Docker daemon. On Ubuntu, run

sudo service docker stop

Then move the old /var/lib/docker out of the way:

sudo mv /var/lib/docker /var/lib/docker~

Now create a directory on /home:

sudo mkdir /home/docker

and set the required permissions:

sudo chmod 0711 /home/docker

Link the /var/lib/docker directory to the new working directory:

sudo ln -s /home/docker /var/lib/docker

Then restart the Docker daemon:

sudo service docker start

Then it should work again.

For future reference, if you have removed all the containers you can also try docker system prune which will remove dangling images, containers and anything else.