openjdk-8-jre-headless : Depends: ca-certificates-java but it is not going to be installed

is this jessie? With backports

apt install -t jessie-backports  openjdk-8-jre-headless ca-certificates-java

It is not working from Jessie backports. I tried stretch and it got installed.

echo 'deb http://ftp.au.debian.org/debian/ stretch main contrib non-free' > /etc/apt/sources.list.d/stretch.list && \
apt-get update && \
apt-get install -y --no-install-recommends openjdk-8-jre-headless && \
rm /etc/apt/sources.list.d/stretch.list && \
apt-get clean && \
rm -rf /var/lib/apt/lists/*

P.S.: I used an Australian mirror since I am here. Choose the best for you from here.

this worked for me many thanks, note you got an extra 'deb' in your echo i had to remove, i am also in Oz but this should work on all repos by now, seems it was an issue with certificates for fixed list of java versions

https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=851667