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.

Erwägungen:
1.
1.1. Der Beschwerdeführer macht geltend, die Weiterführung der Verwahrung sei nicht verhältnismässig und mit Bundes- sowie Verfassungsrecht unvereinbar. Zur Begründung führt er aus, die vorinstanzliche Einschätzung betreffend Gefahr beziehungsweise Schwere von erneuten Delikten finde keine Grundlage in den Akten. Zudem seien mildere Massnahmen, beispielsweise eine engmaschige Überwachung im Rahmen von erwachsenenschutzrechtlichen Massnahmen, denkbar. Schliesslich würden seine persönlichen Interessen die öffentlichen Interessen überwiegen. Mit der Abweisung seines Gesuchs um unentgeltliche Rechtspflege und Rechtsverbeiständung verletze die Vorinstanz schliesslich Art. 29 Abs. 3 BV.
1.2. Das Bundesgericht befasste sich im Urteil 6B_1147/2018 vom 25. März 2019 (Rückweisungsentscheid) zunächst mit den Rügen des Beschwerdeführers zu der vorinstanzlichen Einschätzung seiner Entlassungsprognose. In diesem Zusammenhang hielt es fest, es sei nicht willkürlich, wenn die Vorinstanz zum Schluss gelange, das gutachterlich attestierte deutlich aktuelle Risiko für Gewaltdelikte umfasse auch schwere Körperverletzungen. Insgesamt sei der Entscheid der Vorinstanz betreffend die Gefährlichkeit des Beschwerdeführers zumindest nachvollziehbar (a.a.O., E. 1.4). In der Folge prüfte das Bundesgericht die Einwände gegen die vorinstanzliche Verhältnismässigkeitsprüfung. Diese erachtete es als ungenügend, weshalb es die Sache an die Vorinstanz zurückwies. Es erwog, die Vorinstanz äussere sich weder zur Schwere der vom Beschwerdeführer zu erwartenden Delikte noch zu den bedrohten Rechtsgütern und deren Gewichtung. Auch dem Gutachten lasse sich zur expliziten Frage nach der Schwere erneuter Delikte keine Angaben entnehmen. Folglich nehme die Vorinstanz keine Interessensabwägung vor. Ebenso wenig begründe sie, weshalb keine mildere Massnahme möglich sei. Dies habe sie nachzuholen. Dabei werde die Vorinstanz prüfen müssen, ob das Gutachten vom 22. November 2017 ergänzungsbedürftig sei (a.a.O., E. 2.4).
1.3. Heisst das Bundesgericht eine Beschwerde gut und weist es die Angelegenheit zur neuen Beurteilung an die Vorinstanz zurück, darf sich diese von Bundesrechts wegen nur noch mit jenen Punkten befassen, die das Bundesgericht kassierte. Die anderen Teile des Urteils haben Bestand und sind in das neue Urteil zu übernehmen. Irrelevant ist, dass das Bundesgericht mit seinem Rückweisungsentscheid formell in der Regel das ganze angefochtene Urteil aufhebt. Entscheidend ist nicht das Dispositiv, sondern die materielle Tragweite des bundesgerichtlichen Entscheids. Die neue Entscheidung der kantonalen Instanz ist somit auf diejenige Thematik beschränkt, die sich aus den bundesgerichtlichen Erwägungen als Gegenstand der neuen Beurteilung ergibt. Das Verfahren wird nur insoweit neu in Gang gesetzt, als dies notwendig ist, um den verbindlichen Erwägungen des Bundesgerichts Rechnung zu tragen (<ref-ruling> E. 5.2.1 S. 220 mit Hinweisen). Die mit der neuen Entscheidung befasste Instanz hat ihrem Urteil die rechtliche Beurteilung zugrunde zu legen, mit der die Rückweisung begründet wird. Jene bindet auch das Bundesgericht, falls ihm die Sache erneut unterbreitet wird (<ref-ruling> E. 2 und 2.1 S. 335 f. mit Hinweisen; Urteil 6B_739/2019 vom 2. September 2019 E. 2.2).
1.4. Wie die Vorinstanz zutreffend festhält, hatte sie einzig die Verhältnismässigkeitsprüfung zu wiederholen. Die übrigen Punkte ihres Urteils wurden entweder nicht angefochten oder vom Bundesgericht bestätigt. Nicht einzutreten ist daher auf den neuen Antrag des Beschwerdeführers, es sei ihm für das Verfahren vor der Vorinstanz die unentgeltliche Rechtspflege sowie unentgeltliche Rechtsverbeiständung zu gewähren und die Vorinstanz sei anzuweisen, den unentgeltlichen Rechtsbeistand angemessen zu entschädigen. Der Beschwerdeführer focht die Verweigerung der unentgeltlichen Prozessführung und Rechtsverbeiständung in seiner ersten Beschwerde in Strafsachen nicht an, weshalb sie nie Gegenstand des bundesgerichtlichen Verfahrens und nicht von der Rückweisung betroffen war.
1.5.
1.5.1. Die Vorinstanz erwägt im Rahmen ihrer Verhältnismässigkeitsprüfung zusammengefasst, der 62-jährige Beschwerdeführer befinde sich seit dem 1. September 2008 und damit seit über zehn Jahren in der Verwahrung. Zuvor sei kurzzeitig eine stationäre therapeutische Massnahme angeordnet gewesen. Der Eingriff in seine Freiheitsrechte erreiche auch mit Blick auf die ausgefällte Strafe von neun Monaten mittlerweile eine mittlere Schwere. Es seien Gewalttaten nach der Art der bisherigen zu erwarten, wofür ihm ein deutlich aktuelles Risiko attestiert werde. Auch wenn der Beschwerdeführer bislang keines seiner Opfer in schwerwiegender Weise verletzt habe, würden seine Gewalthandlungen (würgen, Messerstich in Brust, Schlagen auf Halsschlagader, Kopf auf Boden schlagen) doch das Risiko bergen, schwere körperliche Schäden, mit bis zu möglicher Todesfolge zu verursachen. Somit seien die hochrangigen Rechtsgüter von Leib und Leben betroffen und in nicht unbedeutendem Umfang gefährdet. Weiter sei die Wahrscheinlichkeit und Schwere von Sexualdelikten in die Verhältnismässigkeitsprüfung einzubeziehen. Das Risiko in Bezug auf Sexualdelikte sei nur äussert gering, soweit der Beschwerdeführer seine Medikamente einnehme. Sollte der Beschwerdeführer jedoch seine Medikamente nicht mehr einnehmen und wieder eine Partnerschaft eingehen, erhöhe sich das Risiko eines Sexualdelikts und auch die mögliche Ansteckung mit dem HI-Virus. Das fortschreitende Alter des Beschwerdeführers habe bislang nicht zu einer Abnahme seiner Gefährlichkeit geführt, treibe er doch regelmässig Sport, verneine körperliche Probleme, fühle sich gut und seine körperliche Gesundheit sei aufgrund der HIV-Erkrankung nicht beeinträchtigt. Insgesamt würden die erheblichen öffentlichen Interessen am Schutz der bedrohten Rechtsgüter potenzieller Opfer die privaten Interessen des Beschwerdeführers an der Wiedererlangung seiner Freiheit überwiegen. In der Folge begründet die Vorinstanz, weshalb keine mildere Massnahme zur Verfügung steht und gelangt zum Schluss, dass sich die Verwahrung weiterhin als verhältnismässig erweist (Urteil S. 7 ff.).
1.5.2. Damit kommt die Vorinstanz der Kritik im Rückweisungsurteil grundsätzlich nach und prüft die Verhältnismässigkeit der Verwahrung. Unberücksichtigt lässt sie dabei jedoch die Aufforderung des Bundesgerichts, bei ihrer neuen Entscheidung zu prüfen, ob das Gutachten vom 22. November 2017 ergänzungsbedürftig ist. Auch in ihrer Zusammenfassung des Rückweisungsentscheids erwähnt sie die bundesgerichtlichen Hinweise zum Gutachten nicht (Urteil S. 4). Das Bundesgericht erwog in diesem Zusammenhang, die Gutachterin habe die ihr ausdrücklich unterbreitete Frage, mit welcher Schwere von Gewalt- und Sexualdelikten konkret zu rechnen sei, nicht beantwortet. Die Vorinstanz werde bei ihrer Beurteilung der Verhältnismässigkeit auch prüfen müssen, ob das Gutachten ergänzungsbedürftig sei (Urteil 6B_1147/2018 vom 25. März 2019 E. 2.4). Aus dem angefochtenen Urteil ergibt sich nicht, ob sich die Vorinstanz mit der aufgeworfenen Frage auseinandersetzte und weshalb sie gegebenenfalls von der Ergänzung des Gutachtens absieht. Damit setzt die Vorinstanz einerseits die bundesgerichtlichen Vorgaben nicht um. Andererseits kann das Bundesgericht nicht überprüfen, ob die Vorinstanz Bundes- oder Verfassungsrecht verletzt, indem sie das Gutachten nicht ergänzen lässt. Um weitere Leerläufe zu vermeiden und angesichts der Tatsache, dass seit der Erstellung des Gutachtens zwei Jahre verstrichen sind, ist die Vorinstanz nun anzuweisen, das Gutachten vom 22. November 2017 hinsichtlich der Frage der konkret vom Beschwerdeführer zu erwartenden Gewalthandlungen beziehungsweise deren Schwere ergänzen zu lassen. Ferner erscheint sinnvoll, dass die Gutachterin ihre Einschätzung der Höhe der Rückfallgefahr hinsichtlich Gewalt- und Sexualdelikten aktualisiert.
Mangels hinreichender tatsächlicher Feststellungen kann das Bundesgericht noch nicht prüfen, ob die vorinstanzliche Einschätzung, wonach die Verwahrung weiterhin verhältnismässig ist, bundesrechtskonform ist. Mit der vorliegenden erneuten Rückweisung soll die Frage jedenfalls nicht präjudiziert werden. Auf die Rügen des Beschwerdeführers ist grundsätzlich nicht einzugehen. Zum jetzigen Zeitpunkt rechtfertigt sich einzig, die Vorinstanz darauf hinzuweisen, dass sie bei ihrer Beurteilung die gesamte Zeit, in der dem Beschwerdeführer die Freiheit entzogen war, berücksichtigen muss (Urteil S. 6; Beschwerde S. 9).
2.
Die Beschwerde ist gutzuheissen, soweit darauf eingetreten werden kann. Das vorinstanzliche Urteil ist aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen.
Es sind keine Kosten zu erheben (Art. 66 Abs. 4 BGG). Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs.1 und 2 BGG). Da dieser um unentgeltliche Rechtspflege und Verbeiständung ersucht, ist die Parteientschädigung praxisgemäss seinem Rechtsbeistand auszurichten. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Das Urteil des Verwaltungsgerichts des Kantons Zürich vom 28. Juni 2019 wird aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Zürich hat Rechtsanwalt Simon Epprecht für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 20. November 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Andres