Sachverhalt: A. Das Obergericht des Kantons Zürich verurteilte X._ am 4. Juli 2003 wegen mehrfacher sexueller Handlungen mit Kindern und mehrfacher sexueller Nötigung zu vier Jahren und vier Monaten Zuchthaus als Zusatzstrafe zu einer Strafe gemäss Urteil des Pariser Appellationsgerichts vom 16. Juni 1995. Das Obergericht schob den Vollzug der Strafe zugunsten einer Verwahrung nach Art. 43 Ziff. 1 Abs. 2 aStGB auf. Es beschloss am 1. März 2010, die altrechtliche Verwahrung nach neuem Recht weiterzuführen. X._ befindet sich in der Justizvollzugsanstalt (JVA) Pöschwies. B. X._ beantragte am 12. Dezember 2014, er sei aus der Verwahrung bedingt zu entlassen. Eventualiter sei er in eine offene Vollzugseinrichtung zu versetzen. Er stellte weiter das Gesuch um Einholung eines Therapieberichts. Diese Anträge wies das Amt für Justizvollzug des Kantons Zürich am 5. Januar 2015 ab. Einen Rekurs von X._ gegen diesen Entscheid wies die Justizdirektion des Kantons Zürich am 7. April 2015 ebenso ab wie dessen Gesuch um unentgeltliche Rechtspflege. Die dagegen gerichtete Beschwerde wies das Verwaltungsgericht des Kantons Zürich unter Verweigerung der Gewährung der unentgeltlichen Rechtspflege am 22. Dezember 2015 ab. C. Mit Beschwerde in Strafsachen beantragt X._, das Urteil des Verwaltungsgerichts vom 22. Dezember 2015 sei aufzuheben und die Beschwerde an das kantonale Verwaltungsgericht gutzuheissen. Er sei sofort bedingt aus der Verwahrung zu entlassen. Eventualiter sei er in den offenen Vollzug zu versetzen. Subeventualiter sei die Sache zur neuerlichen Beurteilung und Vervollständigung des Verfahrens an die kantonalen Instanzen zurückzuweisen. Die Kosten seien auf den Staat zu nehmen und seinem Rechtsvertreter sei eine Parteientschädigung für die kantonalen Rekurs- und Beschwerdeverfahren sowie für das bundesgerichtliche Verfahren zuzusprechen. Eventualiter sei ihm für die kantonalen und bundesgerichtlichen Verfahren die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.