Estou respondendo do ponto de vista da RPM, mas tenho certeza de que o DEB tem algo parecido no lugar.
Cada pacote tem Fornece e Requer, eles não precisam corresponder ao nome do pacote. Por exemplo, o OpenJDK fornece java e java-devel. E todos os pacotes que o Requer também o irão agarrar.
O problema é que não há outros provedores para java e java-devel, Oracle JDK não pode ser redistribuído por licença, raramente alguém se importa com empacotamento IBM ou Azul JDK, outras implementações de JVM não são suficientemente completas.
Portanto, a única solução para o seu problema é:
1. estabelecer as alternativas sugeridas por aramboi.
2. crie um pacote sintético que não tenha nada dentro, mas forneça java e / ou java-devel.
Esse será o truque para fazer o dpkg achar que você tem tudo o que é necessário e ele não fará mais o download do openjdk. Cerca de 8 anos atrás, isso poderia causar problemas com o software vinculado ao libjvm.so, mas duvido que tenha sobrado algo que ainda esteja vinculado ao libjvm.so em vez de apenas executar os executáveis java.