Sachverhalt: A. Gegen X._ wurden in der Vergangenheit wegen wiederholter Brandstiftung, Verursachung einer Feuersbrunst und zahlreicher Vermögensdelikte mehrmals Zuchthausstrafen ausgesprochen, die zugunsten einer altrechtlichen Verwahrung nach Art. 43 Ziff. 1 Abs. 2 aStGB aufgeschoben wurden (vgl. Urteil des Obergerichts des Kantons Zürich vom 25. Juli 1984, Urteil des Bezirksgerichts Obertoggenburg vom 14. Februar 1986, Urteil des Bezirksgerichts Horgen vom 20. Juni 1995). Der Vollzug der Verwahrung erfolgte anfänglich in der psychiatrischen Klinik Rheinau. Am 20. Februar 1992 wurde X._ mit Wirkung ab 14. März 1992 provisorisch aus dem Vollzug entlassen. Wegen erneuter einschlägiger Delinquenz wurde er am 24. Mai 1995 in die Verwahrung zurückversetzt und zum Vollzug in die kantonale Strafanstalt Pöschwies eingewiesen. In der Folge erhielt X._ schrittweise Vollzugserleichterungen. Am 4. Juli 2003 wurde er in den offenen Vollzug versetzt. Gleichzeitig wurden ihm unbegleitete Beziehungsurlaube bis zu 32 Stunden bewilligt. Die Bezirksanwaltschaft Zürich befand X._ mit Strafbefehl vom 20. Februar 2004 der mehrfachen Pornographie im Sinne von Art. 197 Ziff. 3bis StGB für schuldig und bestrafte ihn mit fünf Tagen Gefängnis. In Missachtung des genehmigten Urlaubsprogramms hatte er in einem Internet-Café unerlaubte Internetseiten mit Kinderpornographie angeschaut und diese zu speichern versucht. Eine spätere Durchsuchung seines Zimmers ergab, dass er bei früheren Besuchen dieses Cafés bereits entsprechende Bilder auf die Festplatte seines Computers heruntergeladen hatte. X._ wurde deshalb am 7. April 2004 in den geschlossenen Vollzug zurückverlegt, und es wurden ihm nur noch begleitete Beziehungsurlaube bis zu 12 Stunden bewilligt. Nach erneuter Versetzung in den offenen Vollzug im Dezember 2004 wurde X._ am 20. April 2006 anlässlich eines Urlaubs zwecks Besuchs einer Gruppentherapie abermals in einem Internet-Café angetroffen. Da der Verdacht bestand, er habe sich Bilder kinderpornographischen Inhalts angeschaut, wurde er am 17. Juli 2006 in den geschlossenen Verwahrungsvollzug zurückversetzt, und es wurden ihm sämtliche Vollzugslockerungen entzogen. Das eingeleitete Strafverfahren wegen Pornographie im Sinne von Art. 197 Ziff. 3bis StGB wurde am 14. September 2007 eingestellt. B. Infolge der Revision des Allgemeinen Teils des Strafgesetzbuches überprüfte das Obergericht des Kantons Zürich auf Antrag des Sonderdienstes des Amts für Justizvollzug des Kantons Zürich hin die Verwahrung von X._. Am 6. Februar 2008 beschloss es, dass keine therapeutische Massnahme im Sinne von Art. 59-61 oder 63 StGB angeordnet und die Verwahrung nach neuem Recht weitergeführt wird. Die dagegen gerichtete kantonale Nichtigkeitsbeschwerde wies das Kassationsgericht des Kantons Zürich am 8. Mai 2009 ab, soweit es darauf eintrat. C. X._ gelangt mit Beschwerde in Strafsachen an das Bundesgericht. Er beantragt die Aufhebung der angefochtenen Entscheide des Ober- und des Kassationsgerichts und die Anordnung einer stationären therapeutischen Massnahme im Sinne von Art. 59 StGB. Eventualiter sei die Sache zur Neubeurteilung nach Einholung eines Gutachtens über seine Massnahmefähigkeit an die kantonalen Instanzen zurückzuweisen. Überdies ersucht er um Gewährung der unentgeltlichen Rechtspflege. D. Das Obergericht, das Kassationsgericht und die Oberstaatsanwaltschaft des Kantons Zürich verzichteten auf eine Vernehmlassung zur Beschwerde. 