Sachverhalt:
A. Das Obergericht des Kantons Zürich verurteilte X._ am 4. Juli 2003 wegen mehrfacher sexueller Handlungen mit Kindern und mehrfacher sexueller Nötigung zu vier Jahren und vier Monaten Zuchthaus als Zusatzstrafe zu einem Urteil des Pariser Appellationsgerichts vom 16. Juni 1995. Es schob den Vollzug der Freiheitsstrafe zugunsten einer Verwahrung auf und beschloss am 1. März 2010, diese nach neuem Recht weiterzuführen.
Das Gesuch X._s um bedingte Entlassung und eventualiter Versetzung in den offenen Vollzug blieb aufgrund der als nicht unerheblich beurteilten Flucht- und Rückfallgefahr erfolglos (vgl. Urteil 6B_427/2011 vom 26. September 2011).
B. X._ beantragte am 2. Dezember 2009 die Gewährung begleiteter Urlaube. Die Direktion der Justizvollzugsanstalt (JVA) Pöschwies lehnte das Gesuch mit Verfügung vom 12. Februar 2010 ab. Den von X._ am 24. November 2010 dagegen erhobenen Rekurs hiess die Justizdirektion des Kantons Zürich teilweise gut und wies die Angelegenheit an die Direktion der JVA Pöschwies zur neuen Entscheidung zurück. Diese beurteilte das Gesuch am 17. Februar 2011 erneut abschlägig. Ein Rekurs von X._ an die Justizdirektion des Kantons Zürich blieb ebenso ohne Erfolg wie die Beschwerde an das Verwaltungsgericht des Kantons Zürich, welches das Rechtsmittel am 19. Oktober 2011 abwies.
C. Mit Beschwerde in Strafsachen beantragt X._, das verwaltungsgerichtliche Urteil vom 19. Oktober 2011 sei aufzuheben und ihm seien begleitete Urlaube zu gewähren. Die Sache sei an die Vorinstanz zurückzuweisen zur Einholung einer Gutachtensergänzung bei Dr. A._, einer ärztlichen Beurteilung seines Gesundheitszustands (insbesondere zur Mobilität und Fluchtfähigkeit) sowie eines Berichts der JVA Pöschwies zu den Modalitäten eines begleiteten Beziehungsurlaubs. X._ ersucht zudem um unentgeltliche Rechtspflege und Verbeiständung.
D. Das Verwaltungsgericht beantragt in seiner Stellungnahme, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Amt für Justizvollzug des Kantons Zürich und die Direktion der Justiz und des Innern schliessen in ihren Eingaben auf Beschwerdeabweisung.

Erwägungen:
1. <ref-law> enthält eine Rahmenvorschrift zum Hafturlaub. Danach ist dem Gefangenen zur Pflege der Beziehungen zur Aussenwelt, zur Vorbereitung seiner Entlassung oder aus besonderen Gründen in angemessenem Umfang Urlaub zu gewähren, soweit sein Verhalten im Vollzug dem nicht entgegensteht und keine Gefahr besteht, dass er flieht oder weitere Straftaten begeht. <ref-law> gilt für die Beziehungen des Eingewiesenen im Massnahmenvollzug zur Aussenwelt sinngemäss, sofern nicht Gründe der stationären Behandlung weitergehende Einschränkungen gebieten (<ref-law>). Die Einzelheiten der Urlaubsgewährung richten sich nach kantonalem Recht, vorliegend nach der Justizvollzugsverordnung (JVV) des Kantons Zürich vom 6. Dezember 2006 und den Richtlinien der Ostschweizerischen Strafvollzugskommission über die Ausgangs- und Urlaubsgewährung vom 7. April 2006.
2. Das Verhalten des Beschwerdeführers im Verwahrungsvollzug ist unstreitig als insgesamt gut bewertet worden. Es steht einem begleiteten Beziehungsurlaub auch nach Auffassung der Vorinstanz nicht entgegen. Diese bejaht indessen eine Fluchtgefahr. Der Beschwerdeführer habe bereits in jungen Jahren und während eines Grossteils seines Erwachsenenlebens oft andere Länder bereist und dort gelebt. Den Strafverfolgungsbehörden habe er sich während der jeweiligen Strafuntersuchungen in der Schweiz nicht zur Verfügung gehalten, was eine internationale Ausschreibung zur Verhaftung notwendig gemacht habe. Dieser Schritt habe zweimal ausgelöst werden müssen. Von England und Frankreich sei der Beschwerdeführer an die Schweiz ausgeliefert worden. Diese Vorkommnisse, gepaart mit dessen umfangreichen Sprachkenntnissen und den häufigen früheren Auslandaufenthalten, deuteten auf eine nicht unerhebliche Fluchtgefahr hin. Die Gefahr werde dadurch verstärkt, dass der Beschwerdeführer angesichts der beschlossenen Weiterführung der Verwahrung sowie der Verweigerung der bedingten Entlassung und der Versetzung in den offenen Vollzug nicht mit einer baldigen Entlassung rechnen könne und sich möglicherweise noch längere Zeit im Verwahrungsvollzug befinden werde. Auch sein beeinträchtigter Gesundheitszustand stelle die Fluchtgefahr nicht in ein anderes Licht. Zwar lägen bei ihm Schmerzen und gewisse Einschränkungen im Bewegungsapparat vor. Dass er dauernd auf Krücken angewiesen wäre, lasse sich den (Vollzugs-)Berichten jedoch nicht entnehmen. Vielmehr brauche er manchmal keine Krücken. Er sei demnach keineswegs immobil und immerhin noch zu 50 % arbeitsfähig. Der Beschwerdeführer räume in seinem Schreiben vom 16. März 2011 an die Anstaltsdirektion ein, er bedürfe bezüglich seiner gesundheitlichen Probleme keiner aktiven Hilfe Dritter. Sein Gesundheitszustand sei insgesamt etwa gleich wie vor seinem Wechsel in die Abteilung für Suchtgefährdete und Pensionäre im Juli 2010. Im genannten Schreiben ersuche er überdies um eine Beschäftigung in der Garage, im technischen Dienst, in der Küche, Bäckerei oder in der Gärtnerei. Es handle sich dabei um Tätigkeiten, die eine gewisse Gesundheit und Beweglichkeit voraussetzten. Es sei daher nicht rechtsverletzend, von einer nicht unerheblichen, durch den Gesundheitszustand des Beschwerdeführers nicht genügend reduzierten Fluchtgefahr auszugehen. Diese Fluchtgefahr, so die Vorinstanz weiter, könne durch eine Begleitperson im vorgesehenen Rahmen nicht beseitigt werden. Dem Beschwerdeführer könnten daher keine begleiteten Beziehungsurlaube bewilligt werden (Entscheid, S. 6 ff. E. 4).
3. 3.1 Die Vorinstanz spricht sich bei der Prüfung des Urlaubsgesuchs nicht zur Rückfall- oder Wiederholungsgefahr aus. Sie lehnt das Gesuch ausschliesslich wegen Fluchtgefahr ab. Ob Fluchtgefahr vorliegt, beurteilt sich anhand der gesamten Lebensumstände des Eingewiesenen (wie beispielsweise familiäre Bindungen, berufliche und finanzielle Situation, Kontakte zum Ausland; vgl. <ref-ruling> E. 3a; Urteil 6B_577/2011 vom 12. Januar 2012 E. 2.2 mit Hinweisen). Diese Beurteilung beinhaltet keine forensisch-psychiatrische Fragestellung. Das Fachwissen eines medizinischen Sachverständigen ist hier nicht gefragt und eine Begutachtung somit nicht erforderlich. Entsprechend war die Vorinstanz bei der Frage der Gewährung des Hafturlaubs im Hinblick auf die Beurteilung der Fluchtgefahr nicht auf Expertenhilfe angewiesen. Sie musste hierfür nicht auf ein Gutachten abstellen. An der Sache vorbei geht daher der Vorwurf des Beschwerdeführers, die Vorinstanz stütze sich in Verletzung von Bundesrecht (<ref-law> i.V.m. <ref-law>, <ref-law>) auf ungenügende Entscheidgrundlagen, weil sich das Gutachten vom 30. Juni 2009 zur Frage der Fluchtgefahr bei begleiteten Urlauben nicht ausspreche und sie diesbezüglich keine Ergänzung des Gutachtens habe einholen lassen (Beschwerde, S. 6 f.). Der Verfahrensantrag auf Einholung einer Gutachtensergänzung erweist sich aus den gleichen Gründen als unbegründet.
3.2 Die Annahme einer nicht unerheblichen Fluchtgefahr, welche durch den Gesundheitszustand des Beschwerdeführers nicht genügend reduziert sei, stützt die Vorinstanz namentlich auf den Bericht der Fachkommission vom 2. Juli 2010, den Vollzugsbericht vom 28. Dezember 2010, das Protokoll der Vollzugskoordinationssitzung vom 20. April 2010 sowie das Schreiben des Beschwerdeführers vom 16. März 2011 an die Anstaltsdirektion. Diese Entscheidgrundlagen sind nach Auffassung des Beschwerdeführers ungenügend. Die Vorinstanz könne ihren Schluss der hinreichenden Fluchtfähigkeit auf kein einziges aktuelles und verlässliches Aktenstück abstützen (Beschwerde, S. 8-12).
3.2.1 Die Fachkommission setzt sich in ihrem Bericht im Hinblick auf die Beurteilung der Fluchtgefahr eingehend mit dem Beschwerdeführer und seinen Lebensumständen auseinander. Sie untersucht sein Vollzugs- und Sozialverhalten, befasst sich mit seiner Biographie und prüft das soziale Beziehungsnetz. Sie verfügt über umfassende Aktenkenntnisse. Dass sie den Beschwerdeführer persönlich nie gesehen hat, ist unerheblich (Beschwerde, S. 8). Ihre Feststellungen zu den Sprachkenntnissen des Beschwerdeführers, seinen ausgedehnten Auslandaufenthalten, den Ausschreibungen zur Verhaftung und Auslieferungen an die Schweiz finden ihre Stütze im rechtskräftigen Urteil des Obergerichts des Kantons Zürich vom 4. Juli 2003 (kantonale Akten, act. 546, S. 38 f.; S. 159 f.). Die Annahme der Fachkommission, der Beschwerdeführer könnte bei einer Flucht ohne weiteres seine alten Kontakte im Ausland reaktivieren, wurde bereits bei der Beurteilung der Fluchtgefahr des Beschwerdeführers im Verfahren betreffend die Verweigerung der bedingten Entlassung bzw. Versetzung in den offenen Vollzug als nicht willkürlich bezeichnet (Urteil 6B_427/2011 E. 5.3). Darauf kann verwiesen werden. Entgegen der Kritik des Beschwerdeführers wurden sodann nicht alle seine Disziplinierungen gegen das PC-Reglement (namentlich wegen Partitionen zur Verschlüsselung oder Verstecken von Daten) widerrufen (vgl. kantonale Akten, Mappe "Disziplinarwesen"). Die Beurteilung der Fachkommission kann auch unter diesem Gesichtspunkt nicht als "ungesichert" oder "fehleranfällig" bezeichnet werden. Ebenso wenig vermögen die Berichte der Vollzugsveranwortlichen die Beurteilung der Fluchtgefahr durch die Fachkommission in Frage zu stellen, weil jene bei der Einschätzung der Fluchtgefahr von einer andern Ausgangslage ausgingen. Es kann insoweit erneut auf das Urteil 6B_427/2011 verwiesen werden. Inwiefern der Bericht der Fachkommission weder verlässlich noch aktuell sein könnte (Beschwerde, S. 9), ist vor diesem Hintergrund nicht ersichtlich. Die Vorinstanz durfte darauf ohne Willkür abstellen.
Auf das Vorbringen des Beschwerdeführers, die Fachkommission habe ihm das rechtliche Gehör nicht gewährt, ist nicht einzutreten. Der Beschwerdeführer erhebt diesen Einwand erstmals vor Bundesgericht. Die Vorinstanz befasst sich im angefochtenen Entscheid deshalb auch nicht damit. Dass sie sich von Amtes wegen mit dieser Frage hätte auseinandersetzen müssen, macht der Beschwerdeführer mit Recht nicht geltend. Mangels Erschöpfung des kantonalen Instanzenzugs fehlt es insoweit an einem zulässigen Anfechtungsobjekt im Sinne von <ref-law>.
3.2.2 Ebenso wenig können die Beurteilungsgrundlagen zum Gesundheitszustand des Beschwerdeführers im Hinblick auf die Einschätzung der Fluchtgefahr als ungenügend bezeichnet werden. Die Vorinstanz durfte insbesondere gestützt auf die Angaben des Beschwerdeführers im Schreiben an die Anstaltsdirektion vom 16. März 2011 willkürfrei von im Wesentlichen unveränderten gesundheitlichen Verhältnissen ausgehen. Sie hatte deshalb keinen Anlass, die (bisherige) Einschätzung des Gesundheitszustands des Beschwerdeführers unter dem Titel der Aktualität in Frage zu stellen und einen ärztlichen Bericht hierzu einzuholen. Der Verfahrensantrag auf Einholung eines Arztberichts ist daher abzuweisen. Das dem Bundesgericht nachträglich eingereichte ärztliche Zeugnis vom 23. November 2011 von Dr. B._ wurde erst nach dem vorinstanzlichen Entscheid erstellt. Als sogenanntes echtes Novum hat es ausser Betracht zu bleiben (<ref-law>; vgl. <ref-ruling> E. 2.1 S. 344). Gestützt auf die fraglichen Beurteilungsgrundlagen geht die Vorinstanz davon aus, der Beschwerdeführer sei nicht immer auf Krücken angewiesen und zu einem gewissen Grad mobil und bewegungsfähig. Sein eingeschränkter Gesundheitszustand wirke sich nicht (hinreichend) fluchtverhindernd aus. Er vermöge eine Flucht zwar zu erschweren, nicht aber zu verunmöglichen. Was der Beschwerdeführer gegen diese Einschätzung einwendet, überzeugt nicht (S. 10 f.). Er stellt der vorinstanzlichen Beweiswürdigung rein appellatorisch lediglich seine eigene abweichende Sicht der Dinge gegenüber (Beschwerde, S. 11). Bei seiner Kritik verkennt er, dass die von ihm anbegehrten Arbeitstätigkeiten in der Garage, Bäckerei oder Küche eine gewisse körperliche Leistungsfähigkeit und Mobilität voraussetzen und die physische Komponente der Arbeitsfähigkeit Aufschluss über körperliche Ressourcen und Kompetenzen gibt, die ihrerseits Schlüsse auf die Fluchtfähigkeit erlauben.
4. Nach Auffassung der Vorinstanz kann die trotz des angeschlagenen Gesundheitszustands des Beschwerdeführers als nicht unerheblich eingeschätzte Fluchtgefahr durch eine Begleitperson im Rahmen eines Beziehungsurlaubs nicht hinreichend ausgeschaltet werden. Der Beschwerdeführer erachtet diese Beurteilung für nicht ausreichend begründet (<ref-law>) und willkürlich (<ref-law>). Die Vorinstanz setze sich nicht konkret damit auseinander, weshalb eine Urlaubsbegleitung in Anbetracht seines beeinträchtigten Gesundheitszustands nicht in der Lage sein sollte, eine mögliche Flucht zu vereiteln (Beschwerde, S. 10 f., S. 12 f.).
4.1 Aus dem Anspruch auf rechtliches Gehör nach <ref-law> folgt die Verpflichtung der Behörde, ihren Entscheid zu begründen. Sie muss wenigstens kurz die wesentlichen Überlegungen nennen, von denen sie sich hat leiten lassen und auf welche sie sich stützt, sodass der Betroffene den Entscheid in voller Kenntnis der Sache anfechten kann (<ref-ruling> E. 4.1 S. 88 mit Hinweisen).
4.2 Beziehungsurlaube dienen neben therapeutischen Zwecken der Aufrechterhaltung und Pflege von Kontakten des Gefangenen oder Eingewiesenen mit der Aussenwelt (Richtlinien der Ostschweizer Strafvollzugskommission über die Ausgangs- und Urlaubsgewährung vom 7. April 2006, Ziff. 3). § 61 JVV regelt unter Hinweis auf diese Richtlinien Ausgang und Urlaub von Gefangenen. Als begleitete Urlaube gelten solche in Begleitung von Personen des Amts oder von diesem bezeichneten Fachkräften (§ 61 Abs. 3 JVV). Fluchtgefährliche Personen erhalten keinen Urlaub. Sie werden polizeilich vorgeführt, wenn Gründe für einen Sachurlaub bestehen (§ 61 Abs. 4 JVV). Der Beschwerdeführer stellt die Gesetz- und Verfassungsmässigkeit der Urlaubsregelung in der JVV nicht in Frage. Es ist denn auch nicht ersichtlich, inwiefern diese über die gesetzlichen Grundlagen im Strafgesetzbuch (<ref-law>) hinausgehen oder den verfassungsrechtlichen Anforderungen nicht genügen sollten. § 61 JVV hält sich im Rahmen des übergeordneten Rechts.
4.3 Liegt Fluchtgefahr vor, ist die Gewährung von Beziehungsurlauben nach § 61 JVV grundsätzlich nicht möglich. Allerdings sind auch in einem solchen Fall die verschiedenen Interessen gegeneinander abzuwägen und verhältnismässige Lösungen unter Berücksichtigung der konkreten Umstände zu treffen (vgl. ANDREA BAECHTOLD, Strafvollzug, Straf- und Massnahmenvollzug an Erwachsenen in der Schweiz, 2. Aufl., S. 165 Ziff. 134). Sind die Voraussetzungen für eine Urlaubsgewährung nicht vollständig gegeben, ist deshalb zu prüfen, ob sich ein Urlaubsrisiko - eine mögliche Flucht - durch eine Urlaubsbegleitung hinreichend ausschalten lässt (ANDREA BAECHTOLD, Basler Kommentar, Strafrecht I, 2. Aufl. 2007, Art. 84 Rz. 19). Diese Modalität ist nach der bundesgerichtlichen Rechtsprechung namentlich bei Beziehungsurlauben zu prüfen (so Urteil 1P.188/2000 vom 21. Juni 2000 E. 4). Davon gehen der Beschwerdeführer und grundsätzlich auch die Vorinstanz aus (vgl. Entscheid, S. 14).
4.4 Der 65-jährige Beschwerdeführer ist gesundheitlich angeschlagen. Nach den willkürfreien Feststellungen im angefochtenen Entscheid erschweren sein Alter und sein beeinträchtigter Gesundheitszustand zwar eine Flucht, verunmöglichen eine solche aber nicht. Die Vorinstanz erwägt, dass eine Urlaubsbegleitung "im vorgesehenen Rahmen" nicht im Stande wäre, eine Flucht des Beschwerdeführers zu verhindern. Sie verweist damit auf ihre allgemeinen Ausführungen zur Urlaubsgewährung, wonach bei Beziehungsurlauben von Gesetzes wegen keine Begleitung durch Polizeikräfte vorgesehen sei, sondern lediglich durch Personal des Amts oder Fachkräfte, welche eine Flucht nicht zu verhindern vermöchten (vgl. angefochtenen Entscheid, S. 13 f.). Mit diesen Ausführungen legt die Vorinstanz nicht dar, welches die Voraussetzungen für einen begleiteten Beziehungsurlaub sind und inwiefern der Beschwerdeführer diese erfüllt bzw. nicht erfüllt. Ebenso wenig ergibt sich daraus, welches die Modalitäten einer Urlaubsbegleitung sind und wie eine Urlaubsbegleitung konkret ausgestaltet sein müsste, um eine mögliche Flucht des Beschwerdeführers zu verhindern. Der angeschlagene Gesundheitszustand des Beschwerdeführers und die Risiken einer Flucht werden einander nicht gegenübergestellt. Die Vorinstanz spricht sich fallbezogen weder über Art noch Zahl einer zweckmässigen und zumutbaren Urlaubsbegleitung aus. Aus ihren Ausführungen ergibt sich nicht, weshalb eine fachkundige Urlaubsbegleitung mögliche Anstalten des Beschwerdeführers zur Flucht nicht zu verhindern vermöchte. Weiter nimmt die Vorinstanz nicht zur Frage Stellung, ob allenfalls technische Geräte (wie beispielsweise Electronic Monitoring) im Sinne von flankierenden Massnahmen zur weiteren Fluchtsicherung eingesetzt werden könnten. Im Ergebnis ist den Ausführungen der Vorinstanz nicht zu entnehmen, aus welchen Überlegungen das Gesuch des Beschwerdeführers um begleitete Beziehungsurlaube abgelehnt wurde. Ihr Hinweis auf den grossen Ermessensspielraum der Strafvollzugsbehörden bei der Urlaubsgewährung vermag die Pflicht, behördliche Entscheide gemäss <ref-law> hinreichend zu begründen, nicht zu ersetzen. Die Beschwerde ist in diesem Punkt gutzuheissen und der angefochtene Entscheid mangels hinreichender Begründung im Sinne von <ref-law> aufzuheben.
5. Die Beschwerde ist teilweise gutzuheissen. Im Übrigen ist sie abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens hat der Kanton Zürich den Beschwerdeführer im Rahmen seines Obsiegens für das bundesgerichtliche Verfahren zu entschädigen (<ref-law>). Die Entschädigung ist praxisgemäss seinem Rechtsvertreter auszurichten. Insofern wird das Gesuch um unentgeltliche Rechtspflege gegenstandslos. Soweit der Beschwerdeführer mit seiner Beschwerde unterliegt, wird er kostenpflichtig (<ref-law>). Das Gesuch um Gewährung der unentgeltlichen Rechtspflege kann in diesem Umfang gutgeheissen werden. Seine Bedürftigkeit ist ausgewiesen (vgl. <ref-ruling> E. 4) und die Beschwerde war nicht von vornherein aussichtslos. Es sind daher keine Kosten zu erheben (<ref-law>). Dem Vertreter ist aus der Bundesgerichtskasse eine reduzierte Entschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 19. Oktober 2011 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird, soweit es nicht gegenstandslos geworden ist, gutgeheissen. Dem Beschwerdeführer wird Rechtsanwalt Dr. Matthias Brunner als unentgeltlicher Rechtsbeistand beigegeben.
3. Es werden keine Kosten erhoben.
4. Der Kanton Zürich hat dem Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 2'000.-- auszurichten.
5. Dem Rechtsvertreter des Beschwerdeführers wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 1'000.-- aus der Bundesgerichtskasse ausgerichtet.
6. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, Einzelrichterin, sowie der Direktion der Justiz und des Innern des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 3. April 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill