Hola de nuevo,
Escrivo para exponer la solución a mi problema, en caso de que aalguien le suceda lo mismo.
Código:
sudo service apache2 stop
Sudo apt-get purge apache2*
Sudo apt-get autoremove
Rm -Rf /etc/apache2 /usr/lib/apache2 /usr/include/apache2
Con esto eliminamos por completo, pudiendo instalar de nuevo como si nunca hubiera estado en el sistema.
Un saludo