Algo que você instalou depende do Java (geralmente o pacote java-common ). Então você tem que ter um instalado. Você também pode usar pacotes Java do Oracles (por exemplo, usando este método ). Então você pode remover todos os pacotes OpenJDK (e IcedTea) assim:
sudo apt-get purge openjdk* icedtea*
Você manterá o pacote java-common porque o Java agora é fornecido pelos pacotes sun-java *. Se você quiser remover completamente o Java (e ver quais pacotes dependem dele), tente remover o java-common.