Você deve verificar quais pacotes dependem de openjdk-7-jre
sendo instalado e usar
apt-rdepends -r openjdk-7-jre
para removê-los junto com o openjdk-7-jre.
Você pode, no entanto, achar isso impraticável, uma vez eu pensei que poderia me livrar do Java e do Perl em uma máquina servidora Linux e não poderia sem querer quebrar o sistema.