Sachverhalt:
A.
Das Bezirksgericht Zürich verurteilte X._ 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 X._ 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 X._ im Sinne von <ref-law> an.
B.
Am 2. August 2017 lehnte das Amt für Justizvollzug des Kantons Zürich eine bedingte Entlassung aus dem Verwahrungsvollzug ab. X._ erhob dagegen Rekurs bei der Direktion der Justiz und des Innern des Kantons Zürich. Diese wies den Rekurs am 6. April 2018 ab. Die von X._ dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich am 26. September 2018 ab.
C.
X._ beantragt mit Beschwerde in Strafsachen, das Urteil des Verwaltungsgerichts sei aufzuheben und er sei unter Ansetzung einer Probezeit von zwei Jahren aus dem Verwahrungsvollzug zu entlassen. Eventualiter sei die Sache zur Prüfung geeigneter Ersatzmassnahmen an das Verwaltungsgericht zurückzuweisen. X._ ersucht um unentgeltliche Rechtspflege.
D.
Das Verwaltungsgericht und das Amt für Justizvollzug verzichten auf Stellungnahme. Die Oberstaatsanwaltschaft des Kantons Zürich beantragt, die Beschwerde sei abzuweisen.

Erwägungen:
1.
1.1. Der Beschwerdeführer wendet sich gegen die Abweisung seines Antrags auf bedingte Entlassung aus der Verwahrung. Er rügt, die Vorinstanz habe das Gutachten von Dr. A._ vom 22. November 2017 willkürlich falsch gewürdigt, den Sachverhalt unvollständig festgestellt und seinen Anspruch auf rechtliches Gehör verletzt. Dem Gutachten sei entgegen der Schlussfolgerung der Vorinstanz nicht zu entnehmen, das bei ihm festgestellte hohe Basisrisiko für Gewalthandlungen beziehe sich auch auf schwere Körperverletzungen im Sinne von <ref-law>. Die gutachterlichen Aussagen zur Risikoeinschätzung seien bloss mit dem tatnahen Zeitpunkt vom 4. März 2004 in Verbindung zu setzen, klarerweise aber nicht mit dem späteren Zwischenfall mit einem Mitgefangenen vom 10. September 2007. Dieser Vorfall sei zudem weder angezeigt noch verfolgt worden und es sei in Anbetracht der Sanktion von bloss zwölf Tagen Arrest von einer Tätlichkeit auszugehen. Die Gutachterin attestiere ihm bei Fortführung der medizinischen Versorgung nur noch ein deutliches aktuelles Risiko für Gewaltdelikte. Eine sexuelle Motivation für Gewaltdelikte bestehe gemäss Gutachten jedoch nicht mehr. Das Risiko eines erneuten Sexualdelikts sei laut Gutachten sehr gering, da er keinen erhöhten Sexualtrieb mehr aufweise. Die Vorinstanz sei auch nicht darauf eingegangen, dass seine Straftat stark situative Bezüge aufweise.
1.2. Die Vorinstanz stützt sich vorwiegend auf das Gutachten von Dr. A._ vom 22. November 2017. Sie erwägt, dass laut diesem aufgrund der AIDS-Erkrankung des Beschwerdeführers mit HIV-Enzephalopathie und der daraus resultierenden Enthemmung sowie der gesteigerten Rigidität tatzeitnah ein deutliches bis sehr hohes Basisrisiko für weitere Gewalthandlungen im bisherigen Ausmass bestanden habe. Das bisherige Ausmass habe neben einer einfachen Körperverletzung, welche zur Verurteilung geführt habe, auch in einem weiteren Gewaltdelikt im Vollzug bestanden, als der Beschwerdeführer einen Mitinsassen unvermittelt angegriffen und dessen Kopf dreimal auf den Boden geschlagen habe. Diese Handlung sei grundsätzlich, je nach Intensität ihrer Ausführung, dazu geeignet, eine schwere Körperverletzung nach <ref-law> hervorzurufen. Es müsse deshalb davon ausgegangen werden, dass sich die Aussagen bezüglich Rückfallrisiko im Bereich Gewaltdelikte auch auf schwere Körperverletzungen bezogen, zumal die FOTRES-Auswertung zu Gewaltdelikten "Allgemein" erfolgt sei. Das Risiko für Gewaltdelikte, wozu auch die schwere Körperverletzung zähle, sei noch deutlich aktuell und da die Gutachterin auch die grosse Gefahr sehe, dass in einem weniger gesicherten Umfeld das Risiko für eine gewalttätige Auseinandersetzung eskaliere, bestehe noch keine hohe Wahrscheinlichkeit, dass der Beschwerdeführer sich in Freiheit bewähren würde (angefochtenes Urteil, E. 2.3.3 f. S. 5 f.).
Auch bezüglich Sexualdelikte bestünden noch erhebliche Zweifel, ob sich der Beschwerdeführer in Freiheit mit hoher Wahrscheinlichkeit bewähren würde. Das Risiko eines erneuten Sexualdelikts sei zum aktuellen Zeitpunkt gemäss Gutachterin äusserst gering. Sollte er wieder eine intime Beziehung zu einer Partnerin eingehen, müsse diesem Umstand, so das Gutachten, jedoch sorgfältig Rechnung getragen und sein Verhalten engmaschig monitorisiert werden. Inwiefern sich das Risiko wieder erhöhen würde, sollte der Beschwerdeführer die Medikamente absetzen, werde im Gutachten sodann nicht erläutert. Auch wenn er während des Vollzugs seine Medikamente strikt eingenommen und mittlerweile eine Krankheitseinsicht gezeigt habe, stehe damit noch nicht mit grosser Wahrscheinlichkeit fest, dass er auch nach seiner Entlassung und ohne ein streng geführtes Setting die notwendigen Medikamente besorgen, bezahlen sowie einnehmen könne und werde (angefochtenes Urteil, E. 2.4.1 f. S. 7 f.).
1.3.
1.3.1. Nach <ref-law> wird der Täter aus der Verwahrung bedingt entlassen, sobald zu erwarten ist, dass er sich in der Freiheit bewährt. Die in dieser Bestimmung vorausgesetzte Erwartung der Bewährung bezieht sich auf Straftaten im Sinne von <ref-law>. Es muss mithin die ernsthafte Gefahr bestehen, dass der Verwahrte in Freiheit einen Mord, eine vorsätzliche Tötung, eine schwere Körperverletzung, eine Vergewaltigung, einen Raub, eine Geiselnahme, eine Brandstiftung, eine Gefährdung des Lebens oder eine andere mit einer Höchststrafe von fünf oder mehr Jahren bedrohte Tat begehen könnte, welche geeignet ist, die physische, psychische oder sexuelle Integrität einer anderen Person schwer zu beeinträchtigen. Dass sich der Verwahrte in Freiheit anderweitig strafbar machen könnte, steht einer bedingten Entlassung nicht entgegen (<ref-ruling> E. 2.1.1; <ref-ruling> E. 1.1.2.2; je mit Hinweisen).
Die bedingte Entlassung setzt eine günstige Prognose in Bezug auf das künftige Verhalten voraus. Der Massstab für die Beurteilung der Möglichkeit der Entlassung ist sehr streng. Es muss eine entsprechend hohe Wahrscheinlichkeit bestehen, dass sich der Verurteilte in Freiheit bewähren wird (<ref-ruling> E. 2.4 S. 62; <ref-ruling> E. 2.1.1 S. 167; je mit Hinweisen). Die Entlassungsprognose hängt von einer Vielzahl von Faktoren ab. Neben allfälligen Erfahrungen mit Vollzugslockerungen sind auch das Vollzugsverhalten, die Verarbeitung der Straftaten und die zukünftige Lebenssituation zu berücksichtigen. Die Entlassung unmittelbar aus einer Verwahrung in die Freiheit ist praktisch kaum denkbar (Urteil 6B_147/2017 vom 18. Mai 2017 E. 3.1 mit Hinweis).
1.3.2. Das Gericht stützt sich bei seinem Entscheid über die Anordnung einer Verwahrung auf eine sachverständige Begutachtung. Diese muss sich zur Notwendigkeit und den Erfolgsaussichten einer Behandlung des Täters, zur Art und Wahrscheinlichkeit weiterer möglicher Straftaten und zu den Möglichkeiten des Vollzugs der Massnahme äussern (<ref-law>; <ref-ruling> E. 4.3.1 S. 326; Urteil 6B_28/2017 vom 23. Januar 2018 E. 3.3.3).
Das Gericht hat das Gutachten nach fachwissenschaftlichen Kriterien zu verstehen und zu prüfen. Es muss das Gutachten selbstständig beurteilen und darf die Prognoseentscheidung nicht dem Sachverständigen überlassen. Die richterliche Überprüfung bzw. Kontrolle des Gutachtens hat sich deshalb nicht nur auf das ermittelte Prognoseergebnis als solches zu beziehen, sondern muss sich auf die Qualität der gesamten Prognosestellung inklusive der vom Sachverständigen allenfalls verwendeten Prognoseinstrumente erstrecken (Urteil 6B_424/2015 vom 4. Dezember 2015 E. 2.3 mit Hinweis). Das Gericht muss im Ergebnis eine eigenständige Beurteilung des Sachverständigenbeweises im Hinblick auf die Einbeziehung aller für die Begutachtung relevanten Umstände vornehmen, damit es gestützt darauf einen eigenverantwortlichen Entscheid zur Gefährlichkeit treffen kann (Urteil 6B_424/2015 vom 4. Dezember 2015 E. 2.3 mit Hinweis auf Marianne Heer, Basler Kommentar, Strafrecht, Band I, N. 50, N. 53, N. 64d sowie N. 75 zu <ref-law>).
Ob ein Gericht die in einem Gutachten oder Fachbericht enthaltenen Erörterungen für überzeugend hält oder nicht und ob es dementsprechend den Schlussfolgerungen der Experten folgen soll, ist eine Frage der Beweiswürdigung, die mit Beschwerde an das Bundesgericht wegen Verletzung des Willkürverbots gerügt werden kann. Dasselbe gilt für die Frage, ob ein Gutachten in sich schlüssig ist. Das Gericht darf in Fachfragen nicht ohne triftige Gründe von Gutachten abweichen und muss Abweichungen begründen (<ref-ruling> E. 2.1.3 S. 53; <ref-ruling> E. 6.1 S. 372 f.; je mit Hinweisen). Erscheint ihm die Schlüssigkeit eines Gutachtens in wesentlichen Punkten zweifelhaft, hat es nötigenfalls ergänzende Beweise zur Klärung dieser Zweifel zu erheben. Das Abstellen auf eine nicht schlüssige Expertise bzw. der Verzicht auf die gebotenen zusätzlichen Beweiserhebungen kann gegen das Verbot der Willkür verstossen (vgl. <ref-ruling> E. 2.1.3 S. 53; Urteile 6B_244/2017 vom 12. Februar 2018 E. 1.1.2; 6B_265/2015 vom 3. Dezember 2015 E. 4.2; je mit Hinweisen). Dies trifft etwa zu, wenn das Gericht auf das Gutachten abstellt, obwohl die sachverständige Person die an sie gestellten Fragen nicht beantwortet, ihre Erkenntnisse und Schlussfolgerungen nicht begründet oder diese in sich widersprüchlich sind oder die Expertise sonstwie an Mängeln krankt, die derart offensichtlich und auch ohne spezielles Fachwissen erkennbar sind, dass sie das Gericht nicht hätte übersehen dürfen (Urteile 6B_244/2017 vom 12. Februar 2018 E. 1.1.2; 6B_604/2016 vom 29. November 2016 E. 1.2.2 mit Hinweis).
1.4. Voraussetzung für den Antrag des Beschwerdeführers, bedingt aus dem Verwahrungsvollzug entlassen zu werden, wäre eine positive Entlassungsprognose. Zumindest für gewisse Straftaten ist dem Beschwerdeführer momentan jedoch offensichtlich keine positive Prognose zu attestieren. Dies macht er mit Bezug auf Gewaltdelikte, soweit diese die Schwelle schwerer Körperverletzungen nicht überschreiten, auch selbst nicht geltend.
Welches de r in <ref-law> genannten Delikte zur Anordnung der Verwahrung führte, ist entgegen der Ansicht des Beschwerdeführers unerheblich. Nach <ref-law> wird der Täter aus der Verwahrung bedingt entlassen, sobald zu erwarten ist, dass er sich in der Freiheit bewährt, das heisst, er keine Delikte im Sinne dieser Bestimmung mehr begeht (Urteil 6B_90/2016 vom 18. Mai 2016 E. 3.2). Die vorausgesetzte Erwartung der Bewährung bezieht sich mit anderen Worten auf sämtliche Straftaten im Sinne von <ref-law> und nicht ausschliesslich auf solche, die der Verurteilung zugrunde lagen und zur Anordnung der Verwahrung führten. Mithin steht ein Risiko für die Begehung einer schweren Körperverletzung der bedingten Entlassung des Beschwerdeführers entgegen.
Im Zusammenhang mit der Frage der Schwere der Gewaltdelikte ist in Ergänzung der vorinstanzlichen Erwägungen auf die Feststellung des Bezirksgerichts Zürich im Urteil vom 7. Juli 2005 hinzuweisen. Demnach wurde der Beschwerdeführer wegen einer am 4. März 2004 versuchten Vergewaltigung und einfachen Körperverletzung verurteilt. Zusätzlich erfüllte er jedoch den Tatbestand der schweren Körperverletzung, wenn auch unvollendet und im Zustand der nicht selbstverschuldeten Zurechnungsunfähigkeit.
Aus dem Gutachten von Dr. A._ vom 22. November 2017ergibt sich sodann zumindest keine offensichtliche Beschränkung des vom Beschwerdeführer ausgehenden aktuellen Risikos auf bloss leichte Körperverletzungen oder gar blosse Tätlichkeiten.
Indem die Vorinstanz das Risiko im Bereich Gewaltdelikte auch hinsichtlich schwerer Körperverletzungen im Sinne von <ref-law> und damit einer Tat im Sinne von <ref-law> ohne Zweifel als gegeben erachtet, verfällt sie nicht in Willkür. Ihre diesbezügliche Beweiswürdigung erscheint nicht als schlechterdings unhaltbar. Die Vorinstanz weist zu Recht etwa darauf hin, dass sich die gutachterliche Wertung des Forensischen Operationalisierten Therapie-Risiko-Evaluationssystems (FOTRES) auf "Gewaltdelikte (Allgemein) " und nicht etwa konkret auf die Tat vom 4. März 2004, für welche der Beschwerdeführer vom Bezirksgericht Zürich wegen einfacher Körperverletzung verurteilt worden war, vorgenommen wurde (kant. Akten, act. 8/6, S. 63 f. und Anhang des Gutachtens S. 1).
Der Beschwerdeführer belegt mit seinen Ausführungen, weshalb die Risikoprognose nicht auf schwere Körperverletzungen zu beziehen sei, keine Willkür. Es ist ihm zwar zuzustimmen, dass dem Gutachten an der von ihm zitierten Stelle zunächst zu entnehmen ist, dass "tatzeitnah" ein deutliches bis sehr hohes Basisrisiko für weitere Gewalthandlungen "im bisherigen Ausmass" bestanden habe. Abschliessend, so das Gutachten weiter, komme man aber zu einem deutlichen aktuellen Risiko für Gewaltdelikte in der FOTRES-Wertung (kant. Akten, act. 8/6, S. 78). Dass dieses abschliessend erkannte Risiko entgegen der vorinstanzlichen Schlussfolgerung keine schwere Körperverletzungen umfassen sollte, drängt sich nicht geradezu auf. Dem Gutachten liegen im Einklang mit der Zieldeliktsdefinition "Gewaltdelikte" auch mehrere Delikte während des Vollzugs zugrunde (vgl. etwa kant. Akten, act. 8/6, S. 65). Eine rechtliche Qualifikation der einzelnen Gewaltdelikte ist ohnehin nicht die Aufgabe der Gutachterin. Die Gutachterin trifft soweit ersichtlich denn auch keine Unterscheidung zwischen schweren und leichten Körperverletzungen oder Tätlichkeiten.
Dass der vom Beschwerdeführer als blosse Tätlichkeit bezeichnete Zwischenfall mit einem Mitgefangenen vom 10. September 2007 weder angezeigt noch verfolgt worden sei, ändert an der Plausibilität der vorinstanzlichen Feststellung nichts. Entgegen der Kritik des Beschwerdeführers ist dieser Vorfall zudem in die Risikoeinschätzung des Gutachtens eingeflossen (vgl. kant. Akten, act. 8/6, S. 20 f., 24 und 38).
Des Weiteren erwähnt das Gutachten zusätzliche Vorfälle, jeweils ebenfalls mit Miteingewiesenen (kant. Akten, act. 8/6, S. 28 f.). Die Gutachterin weist insbesondere auf ein Risiko tätlicher Auseinandersetzungen mit Miteingewiesenen hin. Ein letzter deliktsrelevanter Vorfall sei noch vor eineinhalb Jahren beobachtet worden (kant. Akten, act. 8/6, S. 79). Dass auch diese Auseinandersetzungen trotz geltender Offizialmaxime bei schweren Körperverletzungen offenbar nicht zu weiteren Strafverfahren führten, schliesst die vorinstanzliche Schlussfolgerung eines entsprechenden vom Beschwerdeführer ausgehenden Risikos ebenso wenig geradezu aus.
Bei dieser Sachlage ist der Entscheid der Vorinstanz betreffend die Gefährlichkeit des Beschwerdeführers zumindest nachvollziehbar und es ist nicht zu beanstanden, dass sie sich nicht mit dem Umstand situativer Bezüge, welche der Beschwerdeführer vor Bundesgericht näher zu beschreiben unterlässt, auseinandergesetzt habe. Im angefochtenen Entscheid ist hinreichend dargelegt, von welchen Überlegungen sich die Vorinstanz bei ihrer Beweiswürdigung leiten liess. Es ist nicht erforderlich, dass sie sich mit allen Vorbringen einlässlich auseinandersetzt und diese explizit widerlegt (<ref-ruling> E. 4.3.2 S. 436; <ref-ruling> E. 2.2; <ref-ruling> E. 5.1; je mit Hinweisen). Darauf weist zu Recht auch die Beschwerdegegnerin 1 in ihrer Stellungnahme hin. Weshalb es ausserhalb des Vollzugs nicht gar vermehrt zu vergleichbaren Situationen kommen könnte, wie sie bei den bisherigen Vorfällen vorlagen, zeigt der Beschwerdeführer ferner nicht auf.
Angesichts dieses Ergebnisses braucht nicht geprüft zu werden, ob sich der Beschwerdeführer in Freiheit bezüglich Sexualdelikten zum aktuellen Zeitpunkt mit hoher Wahrscheinlichkeit bewähren würde und ob die Vorinstanz bei der Beurteilung dieser Frage gegen das Willkürverbot verstiess.
2.
2.1. Der Beschwerdeführer macht sodann geltend, seine Verwahrung sei unverhältnismässig. Diese dauere schon 18mal länger als die ursprüngliche und bereits verbüsste Freiheitsstrafe. Er sei krank und seine gesundheitliche Entwicklung ungewiss. Die Vorinstanz lasse unbeachtet, dass die Anforderungen zur Wahrung der Verhältnismässigkeit immer strenger würden, je länger die Massnahme dauere. Sie berücksichtige weiter nicht, dass er bald 62 Jahre alt sei. Indem die Vorinstanz diese beiden Aspekte ausser Acht lasse, verletze sie den Grundsatz der Verhältnismässigkeit sowie seinen Anspruch auf rechtliches Gehör.
2.2. Die Vorinstanz erwägt, die Dauer der Verwahrung stehe nicht in einem bestimmten Verhältnis zur ausgefällten Strafe, sondern hänge in erster Linie von der Zeit ab, die zur Besserung des Täters, namentlich zur Verringerung seiner Gefährlichkeit, notwendig sei. Die Gutachterin halte weitere Fortschritte in den kommunikativen Fertigkeiten des Beschwerdeführers für unabdingbar, um ihm einen erfolgreichen Aufenthalt in einem weniger gesicherten Umfeld zu ermöglichen. Aufgrund der aktuellen Einschränkungen bestehe laut Gutachterin die grosse Gefahr, dass der Beschwerdeführer sich nicht rechtzeitig mitteilen könne, hierdurch sein Anspannungsniveau steige und damit das Risiko für eine gewalttätige Auseinandersetzung eskaliere. Mildere Massnahmen als eine Verwahrung seien aufgrund des noch vorhandenen Risikos momentan nicht möglich. Damit erweise sich die Verwahrung weiterhin als verhältnismässig (angefochtenes Urteil, E. 3.2 S. 9).
2.3. Gemäss <ref-law> ist eine Massnahme anzuordnen, wenn eine Strafe alleine nicht geeignet ist, der Gefahr weiterer Straftaten des Täters zu begegnen (lit. a), ein Behandlungsbedürfnis des Täters besteht oder die öffentliche Sicherheit dies erfordert (lit. b) und die Voraussetzungen der Artikel 59-61, 63 oder 64 StGB erfüllt sind (lit. c). Nach <ref-law> setzt die Anordnung einer Massnahme voraus, dass der mit ihr verbundene Eingriff in die Persönlichkeitsrechte des Täters im Hinblick auf die Wahrscheinlichkeit und Schwere weiterer Straftaten nicht unverhältnismässig ist. Die Voraussetzungen von Art. 56 Abs. 1 und 2 StGB müssen stets vorliegen und nach der Rechtsprechung auch im Rahmen von Folgeentscheidungen beachtet werden. Eine Massnahme, für welche die Voraussetzungen nicht mehr erfüllt sind, ist gemäss <ref-law> aufzuheben (Urteile 6B_798/2014 vom 20. Mai 2015 E. 2, nicht publiziert in: <ref-ruling>; 6B_669/2017 vom 27. April 2018 E. 1.2.1).
Bei der im Rahmen von <ref-law> erforderlichen Abwägung der sich widerstreitenden Interessen sind die vom Täter ausgehenden Gefahren zur Schwere des mit der Massnahme verbundenen Eingriffs ins Verhältnis zu setzen. Es kommt insbesondere darauf an, ob und welche Straftaten vom Massnahmeunterworfenen drohen, wie ausgeprägt das Mass der Gefährdung ist und welches Gewicht den bedrohten Rechtsgütern zukommt. Je schwerer die Delikte wiegen, die der Massnahmeunterworfene in Freiheit begehen könnte, desto geringer kann die Gefahr sein, die eine freiheitsentziehende Massnahme rechtfertigt, und umgekehrt (Urteil 6B_823/2018 vom 12. September 2018 E. 2.1; Urteil 6B_109/2013 vom 19. Juli 2013 E. 4.4.3).
2.4. Die Vorinstanz gibt das Gutachten korrekt wieder, wonach weitere Fortschritte der kommunikativen Fertigkeiten des Beschwerdeführers unabdingbar seien, um ihm einen erfolgreichen Aufenthalt in einem weniger gesicherten Umfeld zu ermöglichen (kant. Akten, act. 8/6, S. 80). Weder diese Erkenntnis noch ihre vor dem Willkürverbot standhaltende Feststellung des Risikos für eine schwere Körperverletzung (vgl. E. 1.4 hiervor) entbinden die Vorinstanz indessen von einer umfassenden und sorgfältigen Verhältnismässigkeitsprüfung der weiteren Verwahrung des Beschwerdeführers.
Im Rahmen der ihr obliegenden Verhältnismässigkeitsprüfung äussert sich die Vorinstanz schon zum Mass der Gefährdung durch den Beschwerdeführer nicht. Anlässlich ihrer (vorhergehenden) Prüfung der Voraussetzungen von <ref-law> hält sie nur aber immerhin fest, das von ihm ausgehende Risiko für Gewaltdelikte, wozu auch die schwere Körperverletzung zähle, sei noch deutlich aktuell. Das Risiko eines erneuten Sexualdelikts sei zum aktuellen Zeitpunkt dagegen äusserst gering, doch sei diesbezüglich von einem höheren Rückfallrisiko auszugehen, sollte der Beschwerdeführer wieder eine intime Beziehung zu einer Partnerin eingehen. Auch stehe nicht mit grosser Wahrscheinlichkeit fest, dass er nach seiner Entlassung die notwendigen Medikamente einnehme (vgl. E. 1.2 hiervor).
Sodann und insbesondere enthält das angefochtene Urteil weder Erwägungen zur Schwere der Delikte noch zu den bedrohten Rechtsgütern oder deren Gewichtung. Die mögliche weitere Tat des Beschwerdeführers muss nicht bloss geeignet sein, die physische, psychische oder sexuelle Integrität einer anderen Person schwer zu beeinträchtigen (vgl. E. 1.3 hiervor). Zusätzlich muss sie das Interesse des Beschwerdeführers, seine ihm seit Jahren genommene Freiheit wieder zu erlangen und bedingt entlassen zu werden, vor dem Anspruch potenzieller Opfer auf Schutz zurücktreten lassen. Ohne vorherige Wertung der bereits begangenen und der weiteren befürchteten Delikte und der dadurch bedrohten Rechtsgüter lässt sich diese notwendige Überprüfung der Verhältnismässigkeit im engeren Sinne nicht bundesrechtsgenüglich vornehmen.
Im Übrigen sind auch der Antwort des Gutachtens zur expliziten Frage der Schwere erneuter Delikte keine Angaben zu entnehmen. Die Gutachterin beschränkt sich soweit ersichtlich ebenfalls darauf, das Risiko der Begehung eines erneuten Gewalt- oder Sexualdelikts darzulegen (vgl. kant. Akten, act. 8/6, S. 82 f.).
Mangels Wertung der Delikte und der durch diese bedrohten Rechtsgüter nimmt die Vorinstanz auch keine anschliessende Interessenabwägung mit dem Eingriff in die Persönlichkeitsrechte durch die am 1. September 2008 angeordnete Verwahrung vor. Die Vorinstanz begnügt sich vielmehr damit, die Verw ahrung alleine deshalb als verhältnismässig zu erachten, weil momentan keine mildere Massnahme möglich sei. Dies betrifft lediglich die Erforderlichkeit der Massnahme. Weshalb keine mildere Massnahme möglich sei, etwa eine stationäre Massnahme, wie sie mit dem Urteil vom 7. Juli 2005 angeordnet worden war, begründet sie ebenso wenig. Damit verletzt sie Bundesrecht und die Sache ist deshalb an die Vorinstanz zurückzuweisen, damit sie die Verhältnismässigkeit auch unter diesen Aspekten und entsprechend ihrer daraus zu gewinnenden Erkenntnisse neu entscheidet. Dabei wird die Vorinstanz auch prüfen müssen, ob das Gutachten von Dr. A._ vom 22. November 2017 ergänzungsbedürftig ist. Damit erübrigt sich, auf die weiteren Rügen des Beschwerdeführers zur Missachtung des Verhältnismässigkeitsprinzips und zur Verletzung seines Anspruchs auf rechtliches Gehör einzugehen.
3.
Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer im Umfang seines Unterliegens grundsätzlich kostenpflichtig (<ref-law>). Sein Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist gutzuheissen, da von Bedürftigkeit auszugehen ist und sein Rechtsbegehren nicht aussichtslos war. Es sind keine Kosten zu erheben (Art. 64 Abs. 1 und 66 Abs. 4 BGG). Der Kanton Zürich hat dem Beschwerdeführer für das bundesgerichtliche Verfahren im Umfang seines Obsiegens eine angemessene Entschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG). Diese ist praxisgemäss seinem Rechtsvertreter auszurichten. Insoweit wird das Gesuch um unentgeltliche Rechtspflege gegenstandslos. Im Umfang des Unterliegens ist der Rechtsvertreter des Beschwerdeführers aus der Bundesgerichtskasse zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Das Urteil des Verwaltungsgerichts des Kantons Zürich vom 26. September 2018 wird teilweise aufgehoben und die Sache zu neuer Entscheidung an das Verwaltungsgericht zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf eingetreten wird.
2.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen, soweit es nicht gegenstandslos geworden ist. Ihm wird Rechtsanwalt Simon Epprecht als unentgeltlicher Rechtsbeistand beigegeben.
3.
Es werden keine Gerichtskosten erhoben.
4.
Der Kanton Zürich hat dem Rechtsvertreter des Beschwerdeführers, Rechtsanwalt Simon Epprecht, für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 1'500.-- zu bezahlen.
5.
Der Rechtsvertreter des Beschwerdeführers wird aus der Gerichtskasse mit Fr. 1'500.-- entschädigt.
6.
Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 25. März 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Weber