Sachverhalt:
A. X._ wurde mit Urteil des Obergerichts des Kantons Zürich vom 9. März 2004 des Fahrens in angetrunkenem Zustand verurteilt und mit einer Gefängnisstrafe von 41⁄2 Monaten bestraft. Der Vollzug der Gefängnisstrafe wurde zugunsten einer Verwahrung aufgeschoben. Das Bundesgericht wies die von X._ erhobene eidgenössische Nichtigkeitsbeschwerde ab, soweit es darauf eintrat (Urteil 6S.196/2004 vom 27. Oktober 2004). Seit dem 30. November 2004 befindet sich X._ im Verwahrungsvollzug. Das Obergericht des Kantons Zürich trat am 1. Oktober 2008 auf ein von X._ gestelltes Haftentlassungsgesuch mangels Zuständigkeit nicht ein. Es beschloss, die Verwahrung nach neuem Recht weiterzuführen. Das Bundesgericht wies eine von X._ erhobene Beschwerde in Strafsachen ab, soweit es darauf eintrat (Urteil 6B_33/2009 vom 25. Februar 2009).
B. Der Justizvollzug des Kantons Zürich lehnte im Rahmen der jährlichen Prüfung von Amtes wegen mit Verfügung vom 7. Oktober 2008 die bedingte Entlassung aus der Verwahrung ab. Dagegen rekurrierte X._. Die Direktion der Justiz und des Innern des Kantons Zürich (nachfolgend Justizdirektion) wies am 22. Januar 2009 den Rekurs ab.
X._ ersuchte am 21. August 2008 um Aufhebung der Verwahrung, eventualiter um bedingte Entlassung aus der Verwahrung, sowie um Gewährung von Vollzugslockerungen. Der Justizvollzug wies am 5. Dezember 2008 die Anträge ab. Der von X._ erhobene Rekurs wurde am 5. März 2009 von der Justizdirektion abgewiesen.
X._ führte gegen die Verfügungen der Justizdirektion Beschwerde an das Verwaltungsgericht des Kantons Zürich, welches mit Urteil vom 15. Juli 2009 die beiden Rekursverfahren vereinigte. Die Beschwerde gegen die Verfügung vom 22. Januar 2009 wies es ab. In teilweiser Gutheissung der Beschwerde gegen die Verfügung vom 5. März 2009 hob es die Dispositiv-Ziffer I Abs. 2 der Verfügung insofern auf, als sie den Rekurs gegen die Verweigerung von Vollzugslockerungen abwies. Das Verwaltungsgericht wies die Sache zum Neuentscheid an den Justizvollzug zurück.
C. Mit Beschwerde in Strafsachen beantragt X._, der Entscheid des Verwaltungsgerichts sei aufzuheben, und er sei auf einen vom Gericht zu bestimmenden Zeitpunkt bedingt zu entlassen. Eventualiter sei die Sache zur bedingten Entlassung, subeventualiter zur weiteren Abklärung des Sachverhalts zurückzuweisen. Es sei festzustellen, dass Art. 5 Ziff. 4 EMRK verletzt worden sei. Zudem ersucht X._ um unentgeltliche Rechtspflege und Verbeiständung.

Erwägungen:
1. Die Verwahrung des Beschwerdeführers wurde nach neuem Recht weitergeführt (vgl. <ref-ruling> E. 1.1.1 S. 51 f. mit Hinweisen). Vorliegend bildet Streitgegenstand die Prüfung der bedingten Entlassung aus der Verwahrung. Auf die Vorbringen des Beschwerdeführers, welche sich gegen die Anordnung der Verwahrung richten (s. insbesondere Beschwerde Ziff. 6 bis 9.4), ist nicht einzutreten. Auf die Rüge des Beschwerdeführers, die unzureichende Entscheidbegründung verletze seinen Anspruch auf rechtliches Gehör, ist mangels rechtsgenügender Begründung ebenfalls nicht einzutreten (Art. 106 Abs. 2 BGG).
2. 2.1 Der Täter wird aus der Verwahrung nach Artikel 64 Absatz 1 StGB bedingt entlassen, sobald zu erwarten ist, dass er sich in der Freiheit bewährt (Art. 64a Abs. 1 Satz 1 StGB). Gemäss Art. 64b Abs. 1 lit. a StGB prüft die zuständige Behörde auf Gesuch hin oder von Amtes wegen mindestens einmal jährlich, und erstmals nach Ablauf von zwei Jahren, ob und wann der Täter aus der Verwahrung bedingt entlassen werden kann (Art. 64a Abs. 1).
2.2 Die Vorinstanz stellt fest, dass sich die tatsächlichen Verhältnisse des Beschwerdeführers seit dem Urteil des Obergerichts vom 9. März 2004 nicht verändert haben. Sie verweist deshalb vorab auf die Erwägungen der Justizdirektion. Diese habe auf das Urteil des Obergerichts abgestellt, welches dem Beschwerdeführer ein hohes Gefährdungspotential bezüglich der körperlichen Integrität attestiert habe. Das Obergericht habe befürchtet, dass der Beschwerdeführer aufgrund des deliktischen Vorlebens und der unbewältigten Alkoholproblematik eine schwere Körperverletzung oder gar den Tod eines Opfers bewirken könnte. Dabei habe das Obergericht die Abweichung seiner Prognose zu jener von Gutachter Dr. G._ überzeugend begründet und habe sich zudem auf ein Gutachten von Dr. H._ abgestützt. Da für die bedingte Entlassung nicht allein der Therapiewille des Verwahrten entscheidend sei, habe die Justizdirektion das Fehlen einer erfolgreichen Therapie im Hinblick auf die Bewährungsprognose berücksichtigen dürfen. Dr. G._ habe in seinem Gutachten vom 5. Dezember 2003 aufgrund der sehr negativ verlaufenen Massnahmen und der alkoholbedingten Wesensänderung des Beschwerdeführers von einer erneuten Massnahme abgeraten. Verschiedene Abklärungen der Therapiemotivation und -eignung hätten ergeben, dass dem Beschwerdeführer der Wille fehle, sich mit seinen Problemen auseinanderzusetzen. Zudem sei er infolge seines Verhaltens im Massnahmezentrum M._ im November 2007 in die Verwahrung zurückversetzt worden, so dass keineswegs von einer Bewährung in Freiheit gesprochen werden könne (angefochtenes Urteil E. 4 S. 14 ff.).
2.3 Der Beschwerdeführer bringt vor, die Vorinstanz setze sich über die bundesgerichtliche Rechtsprechung zu aus dem Strafregister entfernten Urteilen hinweg. Die oberinstanzlichen Erwägungen zur Begründung der Gefährdung der öffentlichen Sicherheit beträfen abgesehen von zwei Ausnahmen Delikte, welche ihm nicht mehr vorgehalten werden dürften. Wolle man darüber spekulieren, ob das Obergericht Taten im Sinne von Art. 64 Abs. 1 StGB ernsthaft erwartet habe, so sei zu prüfen, ob das Obergericht diese Erwartung aufgrund entsprechender gutachterlichen Beurteilungen hätte bejahen dürfen. Dr. G._ habe zwar eine erhöhte Gefahr neuerlicher Taten bejaht, die Gefahr der Begehung von solchen Anlasstaten in Übereinstimmung mit Dr. H._ als gering erachtet. Deshalb hätte das Obergericht gar nicht annehmen dürfen, dass eine ernsthafte Erwartung von Delikten nach Art. 64 Abs. 1 StGB bestehe. Schliesslich sei der Verhältnismässigkeitsgrundsatz (Art. 56 Abs. 2 StGB) zu beachten. Er sei zu 41⁄2 Monaten Gefängnis verurteilt worden. Der aus präventiven Gründen erfolgte Freiheitsentzug daure bereits zwanzig Mal länger.
2.4 Gemäss Art. 369 Abs. 7 Satz 2 StGB dürfen aus dem Strafregister entfernte Einträge dem Betroffenen nicht mehr entgegengehalten werden. Aus dem gesetzgeberischen Willen der vollständigen Rehabilitation folgt, dass entfernte Urteile weder bei der Strafzumessung noch bei der Prognosebeurteilung zu Lasten des Betroffenen verwendet werden dürfen (<ref-ruling> E. 2.4 S. 92). Die Vorinstanz führt dazu aus, diese Rechtsprechung könne nicht auf die Situation der Verwahrung übertragen werden, ansonsten jedem Verwahrten nach Ablauf der Frist eine positive Prognose gestellt werden müsste. Dies könne nicht Wille des Gesetzgebers sein, da bei der Verwahrung im Gegensatz zur Strafzumessung die Sicherheit der Allgemeinheit auf dem Spiel stehe, weshalb zur Beurteilung der Gemeingefährlichkeit auch weiter zurückliegende Straftaten berücksichtigt werden dürften (angefochtenes Urteil E. 4.4.3 S. 16). Der Beschwerdeführer bringt zu Recht vor, dass bei Urteilen, die eine Verwahrung enthalten, die Frist erst zu laufen beginnt, wenn die Massnahme aufgehoben wird oder der Betroffene endgültig aus der Massnahme entlassen ist (s. Art. 369 Abs. 6 lit. b StGB). Dies ändert jedoch nichts daran, dass die ungünstige Bewährungsprognose der Vorinstanz im Ergebnis nicht gegen Bundesrecht verstösst. Als verwertbare Vorstrafe verbleibt insbesondere der im Jahre 1994 begangene Raub, welcher zum Deliktskatalog von Art. 64 Abs. 1 StGB gehört. Weiter stützt sich die Vorinstanz auf die Diagnosen der Gutachter, welche dem Beschwerdeführer ein hohes Gefährdungspotential attestieren. Die medizinischen Sachverständigen dürfen für ihre Begutachtung entfernte Verurteilungen berücksichtigen (<ref-ruling> E. 2.5 S. 92 f. mit Hinweisen). Die Vorinstanz beachtet zudem die gescheiterten Therapieversuche sowie die Tatsache, dass der Beschwerdeführer im Jahre 2007 infolge seines Verhaltens in die Verwahrung zurückversetzt wurde. In Würdigung aller Umstände, insbesondere dem hohen Gefährdungspotential des Beschwerdeführers, rechnet die Vorinstanz mit der Möglichkeit, dass dieser eine schwere Körperverletzung oder eine Tötung und somit eine strafbare Handlung innerhalb des in Art. 64 Abs. 1 StGB aufgeführten Deliktskatalogs begehen werde. Demnach ist nicht zu erwarten, dass sich der Beschwerdeführer in Freiheit bewähren würde (s. <ref-ruling> E. 1.1.2.2 S. 53 f. mit Hinweisen).
2.5 Soweit der Beschwerdeführer die Verwahrung als unverhältnismässig rügt, übersieht er, dass die Verwahrung keine Strafe ist, sondern eine sichernde Massnahme, die den Schutz der Allgemeinheit vor einem gefährlichen Straftäter bezweckt. Dementsprechend steht die Dauer der Verwahrung nicht in einem bestimmten Verhältnis zur ausgefällten Strafe, sondern hängt in erster Linie von der Zeit ab, die zur Besserung des Täters, namentlich zur Verringerung seiner Gefährlichkeit, notwendig ist (Urteil 6A.50/2004 vom 11. Januar 2005 E. 3 mit Verweis). Der Beschwerdeführer weist lediglich auf die Dauer der Freiheitsstrafe hin, ohne die Unverhältnismässigkeit näher zu begründen. Zudem stellt sich nicht die Frage der Verhältnismässigkeit der Anordnung der Verwahrung (Art. 56 Abs. 2 StGB), sondern der Weiterführung der Massnahme (Art. 56 Abs. 6 StGB; vgl. E. 1 hiervor). Eine Verletzung von Bundesrecht ist nicht ersichtlich.
2.6 Zusammengefasst verletzt die Vorinstanz kein Bundesrecht, indem sie von einer bedingten Entlassung absieht. Somit erübrigt sich die Behandlung des Eventualantrags auf Rückweisung der Sache zur bedingten Entlassung an die Vorinstanz. Anlässlich seines Subeventualantrages rügt der Beschwerdeführer die Verletzung seines Anspruchs auf rechtliches Gehör, indem die Vorinstanz kein neues Gutachten eingeholt habe. Die Vorinstanz weist auf die unveränderte Untherapierbarkeit des Beschwerdeführers hin (angefochtenes Urteil E. 4.4.4 S. 17). Sie durfte auf frühere Gutachten abstellen, weil diese nicht an Aktualität eingebüsst haben (s. <ref-ruling> E. 4.3 S. 254 mit Hinweisen). Die Rüge ist unbegründet, soweit darauf einzutreten ist (Art. 106 Abs. 2 BGG).
3. Der Beschwerdeführer beantragt die Feststellung der Verletzung von Art. 5 Ziff. 4 EMRK. Er rügt die Verfahrensdauer vor den verschiedenen Instanzen sowie die Abweisung seines Antrags auf mündliche Anhörung.
3.1 Jede Person, die festgenommen oder der die Freiheit entzogen ist, hat das Recht zu beantragen, dass ein Gericht innerhalb kurzer Frist über die Rechtmässigkeit des Freiheitsentzugs entscheidet und ihre Entlassung anordnet, wenn der Freiheitsentzug nicht rechtmässig ist (Art. 5 Ziff. 4 EMRK).
3.2 Die Vorinstanz verneint eine Verletzung des Beschleunigungsgebots durch die unteren Instanzen. Sie führt aus, die rund eineinhalb Monate zwischen der Anhörung und dem Entscheid des Justizvollzugs sowie die ca. zweieinhalb Monate zwischen der Rekurserhebung und dem Rekursentscheid erschienen durchaus angemessen. Mehrere Instanzen seien gleichzeitig mit ähnlichen Anträgen des Beschwerdeführers beschäftigt gewesen und hätten teilweise Entscheide der anderen Instanz abwarten müssen. Da der Beschwerdeführer keine veränderten Umstände geltend gemacht habe, handle es sich vorliegend um die gesetzlich vorgesehene jährliche Verwahrungsüberprüfung von Amtes wegen, bei welcher weniger strenge Anforderungen an das Beschleunigungsgebot gelten würden. Das Beschleunigungsgebot sei in erster Linie auf die Prüfung der Untersuchungshaft und der erstmaligen Anordnung einer Freiheitsstrafe oder Massnahme ausgerichtet (angefochtenes Urteil E. 3 S. 7 ff.).
3.3 Der Beschwerdeführer bringt vor, die Prüfung der bedingten Entlassung habe sowohl insgesamt als auch einzeln vor sämtlichen Instanzen zu lange gedauert. Keine Instanz habe eine Abklärung oder eine andere Verfahrenserweiterung getätigt. Den Akten sei nicht zu entnehmen, dass Verfahrensverzögerungen entstanden seien, indem er Anträge bei verschiedenen Instanzen gestellt habe. Auch sei nicht ihm anzulasten, dass erst die Vorinstanz die Anträge wieder vereinigt habe. Im vorliegenden Verfahren handle es sich nicht um die jährliche Überprüfung von Amtes wegen, da er in seinem Gesuch vom 21. August 2008 neben der bedingten Entlassung ausdrücklich die Aufhebung der Verwahrung beantragt habe. Der Anspruch auf richterliche Haftprüfung bestehe unabhängig davon, ob der Gesuchsteller veränderte tatsächliche Verhältnisse geltend mache. Zur beantragten mündlichen Anhörung bringt der Beschwerdeführer vor, er sei im Vorverfahren angehört worden, der Anspruch bestehe aber in dem von Art. 5 Ziff. 4 EMRK garantierten gerichtlichen Verfahren.
3.4 Die Vorinstanz hat zwei Verfahren vereinigt. Dasjenige der bedingten Entlassung wurde im Rahmen der jährlichen Prüfung von Amtes wegen (Art. 64b Abs. 1 lit. a StGB) eingeleitet (s. Verfügung der Justizdirektion vom 22. Januar 2009, VB.2009.101 Aktennummer 4). Das Verfahren, welches sich auf das vom Beschwerdeführer gestellte Gesuch vom 21. August 2008 bezieht, wurde infolge hängigen Rekurses zur Frage der bedingten Entlassung auf den Streitgegenstand der Gewährung von Vollzugslockerungen und der Bestellung eines unentgeltlichen Rechtsbeistandes verengt (s. Verfügung der Justizdirektion vom 5. März 2009, VB.2009.197 Aktennummer 4). Somit geht die Vorinstanz zutreffend davon aus, dass das als überlang gerügte Verfahren die Prüfung von Amtes wegen und nicht ein Haftentlassungsgesuch nach Art. 5 Ziff. 4 EMRK betrifft. Das Bundesgericht hat bereits im strafrechtlichen Beschwerdeverfahren des Beschwerdeführers gegen das Urteil des Obergerichts vom 1. Oktober 2008 das Verfahren nach Art. 64a f. StGB zur Prüfung der bedingten Entlassung aus der Verwahrung als genügend im Sinne von Art. 5 Ziff. 4 EMRK erklärt. Gemäss bundesgerichtlicher Rechtsprechung besteht bei rechtskräftiger gerichtlicher Verurteilung und Anordnung einer stationären Massnahme kein Anspruch auf jederzeitige Anrufung des Haftrichters (Urteil 6B_33/2009 vom 25. Februar 2009 E. 3.4 mit Hinweis).
Vorliegend betrug das Verfahren vor dem Justizvollzug eineinhalb Monate, das Rekursverfahren zweieinhalb Monate. Bei der vorinstanzlichen Verfahrensdauer von viereinhalb Monaten ist die Verfahrensvereinigung zu beachten. Sämtliche Instanzen haben auf frühere Gutachten abgestellt, was die jeweilige Verfahrensdauer zwar als lange, aber nicht als unvertretbar erscheinen lässt (vgl. Urteil 6A.63/2001 vom 6. August 2001 E. 1d). Dies gilt auch für die Gesamtdauer von elf Monaten. Somit ist keine Verletzung des Beschleunigungsgebots festzustellen.
3.5 Die Vorinstanz verneint gestützt auf Art. 59 Abs. 1 VRG (Verwaltungsrechtspflegegesetz des Kantons Zürich vom 24. Mai 1959; LS 175.2) einen Rechtsanspruch auf mündliche Verhandlung. Der Beschwerdeführer habe seinen Standpunkt ausreichend geltend machen können und sei im Rahmen der jährlichen Überprüfung der bedingten Entlassung am 21. August 2008 angehört worden (angefochtenes Urteil E. 2 S. 6 f.). Dem ist beizustimmen. Die grundrechtlichen Minimalansprüche von Art. 5 Ziff. 4 EMRK gewähren keinen Anspruch auf mündliche Verhandlung (vgl. Urteil 1B_124/2009 vom 18. Juni 2009 E. 5).
4. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang wird der Beschwerdeführer grundsätzlich kostenpflichtig (Art. 66 Abs. 1 BGG). Er beantragt indes unentgeltliche Rechtspflege und Verbeiständung. Seine Begehren waren nicht aussichtslos, und seine Bedürftigkeit ist ausgewiesen (Art. 64 Abs. 1 und 2 BGG), weshalb dem Antrag stattzugeben ist. Der Rechtsvertreter ist aus der Bundesgerichtskasse zu entschädigen (Art. 64 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen. Für das bundesgerichtliche Verfahren wird dem Beschwerdeführer Rechtsanwalt Matthias Brunner als unentgeltlicher Anwalt beigegeben.
3. Es werden keine Gerichtskosten erhoben.
4. Dem Rechtsvertreter des Beschwerdeführers wird Fr. 3'000.-- als Entschädigung aus der Bundesgerichtskasse ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 25. Januar 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Binz