Sachverhalt: A. Das Bezirksgericht Zürich verurteilte A._ am 7. Juli 2005 wegen versuchter Vergewaltigung sowie einfacher Körperverletzung zu neun Monaten Freiheitsstrafe. Gleichzeitig ordnete es eine stationäre Massnahme gemäss Art. 43 Ziff. 1 Abs. 1 aStGB an und schob den Vollzug der Freiheitsstrafe zugunsten dieser Massnahme auf. Zudem stellte es fest, dass A._ die Tatbestände der unvollendet versuchten schweren Körperverletzung sowie des unvollendet versuchten Verbreitens menschlicher Krankheiten im Zustand der nicht selbstverschuldeten Zurechnungsunfähigkeit erfüllt hatte. Am 1. September 2008 ordnete das Bezirksgericht die Verwahrung von A._ im Sinne von Art. 64 Abs. 1 StGB an. B. Am 2. August 2017 lehnte das Amt für Justizvollzug des Kantons Zürich die bedingte Entlassung von A._ aus dem Verwahrungsvollzug ab. Der hiergegen geführte Rekurs von A._ an die Direktion der Justiz und des Innern des Kantons Zürich blieb ebenso ohne Erfolg wie die Beschwerde an das Verwaltungsgericht des Kantons Zürich. Dieses wies die Beschwerde und das Gesuch um Gewährung der unentgeltlichen Prozessführung und Rechtsvertretung am 26. September 2018 ab. Das Bundesgericht hiess die dagegen geführte Beschwerde in Strafsachen am 25. März 2019 teilweise gut, hob das verwaltungsgerichtliche Urteil auf und wies die Sache zu neuer Entscheidung an das Verwaltungsgericht zurück. Im Übrigen wies es die Beschwerde ab, soweit es darauf eintrat (Urteil 6B_1147/2018). C. Das Verwaltungsgericht wies die Beschwerde und das Gesuch von A._ um Gewährung der unentgeltlichen Prozessführung und Rechtsvertretung am 28. Juni 2019 erneut ab. D. A._ beantragt mit Beschwerde in Strafsachen, das verwaltungsgerichtliche Urteil sei aufzuheben und er sei unter Ansetzung einer Probezeit von zwei Jahren aus dem Verwahrungsvollzug zu entlassen. Eventualiter sei das Urteil aufzuheben und die Sache zur Prüfung geeigneter Ersatzmassnahmen, subeventualiter zur Ergänzung des Gutachtens vom 22. November 2017, an die Vorinstanz zurückzuweisen. Es sei ihm für das vorinstanzliche Verfahren die unentgeltliche Rechtspflege und Rechtsverbeiständung zu gewähren und die Vorinstanz sei anzuweisen, den unentgeltlichen Rechtsbeistand angemessen zu entschädigen. Auch vor Bundesgericht ersucht er um unentgeltliche Rechtspflege und Verbeiständung. E. Das Verwaltungsgericht sowie das Amt für Justizvollzug verzichten auf eine Stellungnahme und beantragen die Abweisung der Beschwerde. Die Oberstaatsanwaltschaft des Kantons Zürich stellt und begründet den Antrag, die Beschwerde sei abzuweisen. A._ verzichtet auf eine Replik.