Yey! Eu fiz isso depois de ler mais um pouco. Foi muito chato porque quando você inicializa sem vídeo, você tem que desligar de maneira inapropriada, então no modo de recuperação você obtém primeiro alguns erros.
Mas o objetivo é entrar no modo de recuperação e digitar duas linhas:
mount -o remount,rw /
sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*
Obrigado a Ash pelas suas respostas à minha pergunta.