Eu segui a resposta de Dev com a adição do download de outras dependências manualmente. No total, tive que baixar os seguintes pacotes da página Debian :
libjpeg62-turbo_1.5.1-2_amd64.deb
openjdk-7-jre-headless_7u121-2.6.8-2_amd64.deb
openjdk-7-jre_7u121-2.6.8-2_amd64.deb
openjdk-7-jdk_7u121-2.6.8-2_amd64.deb
e instale-os com
sudo dpkg -i <deb file>
Sempre que a instalação reclamar sobre dependências ausentes, você pode executar
sudo apt-get install -f
para resolvê-los, a menos que a dependência seja um dos pacotes baixados. Nesse caso, você só precisa instalá-los primeiro com o dpkg.
Se você já tiver uma versão do Java instalada, poderá selecionar os binários do OpenJDK usando
sudo update-alternatives --config java
sudo update-alternatives --config javac