Sachverhalt:
A. X._ verbüsst zurzeit in der Strafanstalt Pöschwies die vom Obergericht des Kantons Zürich am 26. Oktober 2007 verhängte Freiheitsstrafe von elf Jahren wegen versuchter vorsätzlicher Tötung. Das ordentliche Ende der Strafe fällt auf den 30. September 2016. Eine bedingte Entlassung (nach Verbüssung von zwei Dritteln der Strafe) wäre frühestens am 31. Januar 2013 möglich. Die Hälfte der Strafe hat X._ am 31. März 2011 erstanden.
B. Am 20. Mai 2009 wurde X._, unter diversen Auflagen, erstmals ein Beziehungsurlaub bewilligt. Die ihm in der Folge regelmässig gewährten 19 Urlaube absolvierte er klaglos.
Mit Eingabe vom 28. Januar 2010 ersuchte X._ um Versetzung in den offenen Strafvollzug. Das Amt für Justizvollzug des Kantons Zürich wies das Gesuch am 13. Oktober 2010 ab. Dagegen führte der Inhaftierte Rekurs, den die kantonale Justizdirektion am 16. Dezember 2010 abwies.
Am 20. November 2010 stellte X._ ein Urlaubsgesuch für den 22. und 23. Januar 2011. Das Gesuch wurde am 28. Januar 2011 abgelehnt. Gegen diesen Entscheid gelangte der Gefangene an die Justizdirektion des Kantons Zürich, welche den Rekurs mit Entscheid vom 18. April 2011 abwies. Die von X._ dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich am 5. Juli 2011 mit dem Hinweis auf Fluchtgefahr ab.
C. X._ erhebt Beschwerde in Strafsachen. Er beantragt, den verwaltungsgerichtlichen Entscheid vom 5. Juli 2011 aufzuheben und ihm weiterhin Beziehungsurlaube im bisherigen Rahmen zu gewähren. Eventualiter sei die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Gleichzeitig ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
D. Das Verwaltungsgericht des Kantons Zürich beantragt mit Eingabe vom 21. November 2011 unter Hinweis auf die Erwägungen im angefochtenen Entscheid die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die kantonale Justizdirektion und das Amt für Justizvollzug stellen am 17. November 2011 bzw. am 30. November 2011 den Antrag, die Beschwerde sei abzuweisen. X._ reichte hierzu keine Stellungnahme mehr ein.

Erwägungen:
1. Der Entscheid über die Nichtgewährung von Hafturlaub ist eine Strafsache gemäss <ref-law>. Die Beschwerde in Strafsachen ist damit gegeben. Der Beschwerdeführer ist zur Beschwerdeerhebung befugt. Er ist durch den verwaltungsgerichtlichen Entscheid in seinen rechtlich geschützten Interessen betroffen (<ref-law>). Das aktuelle Rechtsschutzinteresse ist zu bejahen (vgl. Urteil 1P.708/2005 vom 30. November 2005 E. 1). Der Beschwerdeführer rügt eine Verletzung von <ref-law> sowie von <ref-law>, einen unzulässigen Eingriff in sein verfassungsmässiges Recht auf persönliche Freiheit (<ref-law>), einen Verstoss gegen das Willkürverbot, den Vertrauensschutz und den Grundsatz von Treu und Glauben (<ref-law>) sowie gegen die Begründungspflicht im Sinne des rechtlichen Gehörs (<ref-law>). Die Rügen sind zulässig (<ref-law>).
2. Gemäss <ref-law> 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 Strafvollzug dem nicht entgegensteht und keine Gefahr besteht, dass er flieht oder weitere Straftaten begeht.
2.1 Der Anspruch auf Urlaub hängt davon ab, dass das Verhalten des Gefangenen einer Urlaubsgewährung nicht entgegensteht und keine Rückfall- oder Fluchtgefahr vorliegt. Die Anforderungen an das Verhalten des Gefangenen im Strafvollzug und die Risiken einer Rückfallgefährlichkeit im Sinne von <ref-law> richten sich nach den Massstäben, wie sie bei der bedingten Entlassung nach <ref-law> gelten (Urteil 6B_349/2008 vom 24. Juni 2008 E. 3.2 mit Hinweis). Für die Beurteilung der Fluchtgefahr sind die vom Bundesgericht bei der Anordnung von Untersuchungshaft entwickelten Kriterien heranzuziehen.
2.2 Fluchtgefahr darf nicht bereits angenommen werden, wenn die Möglichkeit der Flucht in abstrakter Weise besteht. Es braucht vielmehr eine gewisse Wahrscheinlichkeit, dass der Inhaftierte, wenn er in Freiheit wäre, sich dem Vollzug der Strafe durch Flucht entzöge. Es müssen konkrete Gründe dargetan werden, die eine Flucht als wahrscheinlich erscheinen lassen. Hierfür sind die gesamten Verhältnisse des Eingewiesenen wie beispielsweise die Lebensumstände, familiäre Bindungen, berufliche und finanzielle Situation sowie Kontakte zum Ausland, in Betracht zu ziehen (<ref-ruling> E. 3a S. 62; <ref-ruling> E. 3d S. 36; Urteil 1B_378/2009 vom 13. Januar 2010 E. 4.1; Urteil 1P.470/2004 vom 15. Oktober 2004 E. 4; vgl. auch Urteil 6B_742/2010 vom 30. September 2010 E. 2.1).
2.3 Ein Urlaubsgesuch darf wegen Fluchtgefahr nur abgelehnt werden, wenn dies verhältnismässig erscheint und dem Vollzugszweck der Wiedereingliederung des Eingewiesenen ausreichend Rechnung getragen wird. Je näher das Strafende rückt, desto gewichtiger wird das öffentliche Interesse, den Gefangenen auf den Wiedereintritt in die Gesellschaft vorzubereiten, indem ihm unter anderem die Gelegenheit gegeben wird, die hierfür notwendigen persönlichen und familiären Beziehungen zu pflegen oder aufzubauen. Gleichzeitig nimmt das öffentliche Interesse an der vollständigen Vollstreckung einer rechtskräftigen Freiheitsstrafe ab, je länger die Haft bereits gedauert hat. Insofern ist es ein Gebot der Verhältnismässigkeit, gegen Ende des ordentlichen Strafvollzugs ein gewisses Fluchtrisiko bei der Urlaubsgewährung in Kauf zu nehmen, das möglicherweise zu Beginn des Strafvollzugs die Urlaubsgewährung ausschliessen würde (1P.470/2004 E. 5.1). Die Fluchtgefahr ist regelmässig umso geringer einzuschätzen, je kürzer der verbleibende Strafrest ist (CHRISTIAN SCHWARZENEGGER ET AL, Strafrecht II, Strafen und Massnahmen, 8. Auf., 2007, S. 270).
2.4 Im Bereich des Strafvollzugs und damit auch bei der Prüfung von Urlaubsgesuchen kommt den kantonalen Behörden ein weiter Ermessensspielraum zu (Urteil 1P.10/2006 vom 31. Januar 2006 E. 2.4 mit Hinweisen auf die bundesgerichtliche Rechtsprechung). Das Bundesgericht greift in diesen Ermessensspielraum auf Beschwerde in Strafsachen hin nur bei Ermessensüberschreitung bzw. -unterschreitung oder Ermessensmissbrauch ein.
3. 3.1 Die Vorinstanz stellt bei der Beurteilung des Urlaubsgesuchs die ausländerrechtliche Situation des Beschwerdeführers in den Vordergrund. Angesichts seiner Verurteilung zu einer langjährigen Freiheitsstrafe sei damit zu rechnen, dass ihm die Niederlassungsbewilligung entzogen und er aus der Schweiz ausgewiesen werde. Die Annahme von Fluchtgefahr mangels Niederlassungs- bzw. Aufenthaltsbewilligung sei deshalb nicht zu beanstanden, auch wenn sich der Beschwerdeführer im Vollzug wohlverhalten, und er die bisherigen Urlaube klaglos absolviert habe. Das effektive Strafende falle auf den 30. September 2016, und vor einem Entscheid über die bedingte Entlassung sei davon auszugehen, dass der Beschwerdeführer noch eine längere Reststrafe zu verbüssen habe. Die Verweigerung des Urlaubsgesuchs erweise sich auch unter diesem Gesichtspunkt als verhältnismässig (angefochtener Entscheid S. 10).
3.2 Der Beschwerdeführer macht namentlich geltend, die Vorinstanz stelle einseitig auf die Vermutung ab, dass mangels einer Aufenthalts- bzw. Niederlassungsbewilligung Fluchtgefahr anzunehmen sei. Für die Urlaubsverweigerung lasse sie damit die Möglichkeit einer abstrakten Fluchtgefahr genügen. Bei der Beurteilung der Fluchtgefahr sei indes auf konkrete Umstände abzustellen. Die ihm zahlreich gewährten Urlaube, die er klaglos absolviert habe, sprächen gegen Fluchtgefahr. Dasselbe gelte für sein tragfähiges Beziehungsnetz in der Schweiz. Diese und weitere konkrete Umstände (etwa der erschwerte oder gar unmögliche Zugriff auf sein Pensionsguthaben bei Flucht ins Ausland oder das aufs Spielsetzen der möglichen bedingten Entlassung am 31. Januar 2013 mit dem Risiko einer vollständigen Strafverbüssung) lasse die Vorinstanz bei der Beurteilung der Fluchtgefahr in verfassungs- und bundesrechtswidriger Weise ausser Acht (vgl. Beschwerde S. 4 ff.).
4. 4.1 Das Verhalten des Beschwerdeführers im Strafvollzug war unstrittig klaglos. Es steht einem Urlaub auch nach der Auffassung der Vorinstanz nicht entgegen. Zu beantworten bleibt damit die Frage, ob gemäss <ref-law> "keine Gefahr besteht, dass er flieht oder weitere Straftaten begeht". Zur Rückfallgefahr äussert sich die Vorinstanz nicht. Sie bejaht hingegen Fluchtgefahr. Der Beschwerdeführer ist zu einer hohen Freiheitsstrafe von 11 Jahren verurteilt worden. Bei dieser Sachlage und in Anbetracht des dem Beschwerdeführer zur Last gelegten Delikts (versuchte vorsätzliche Tötung) ist das Risiko eines Widerrufs der Niederlassungsbewilligung und der anschliessenden Ausweisung aus der Schweiz nach der Strafverbüssung mit Blick auf die bundesgerichtliche Rechtsprechung nicht nur blosse Hypothese, sondern darf als reale Möglichkeit in Rechnung gestellt werden (vgl. statt vieler Urteil 2C_353/2011 vom 21. Oktober 2011 E. 3 zum Bewilligungswiderruf gemäss Art. 63 Abs. 1 lit. a AuG bei einer versuchten vorsätzlichen Tötung; siehe auch Urteil 1P.10/2006 vom 31. Januar 2006 E. 3.6). Die Aussicht, zusätzlich zur Strafverbüssung aus der Schweiz ausgeschafft zu werden, erhöht die Fluchtgefahr regelmässig in nicht unbeträchtlichem Umfang (Urteil 1B_378/2009 vom 13. Januar 2010 E. 4.1). Davon geht die Vorinstanz im angefochtenen Entscheid aus. Sie stellt insoweit darauf ab, dass der Beschwerdeführer gemäss den Angaben des zuständigen Migrationsamtes "wohl" ausgewiesen werde (angefochtener Entscheid, S. 10). Die Annahme einer gewissen Fluchtgefahr ist insoweit nicht zu beanstanden.
4.2 Allerdings ist eine mögliche oder gar wahrscheinliche Ausweisung aus der Schweiz nach der Strafverbüssung weder einziges noch vorrangiges Kriterium zur Einschätzung der Fluchtgefahr. Hinge es für die Bejahung der Fluchtgefahr ausschliesslich oder überwiegend davon ab, ob die verurteilte Person die Schweiz nach der Strafverbüssung wird verlassen müssen, wären ausländischen Straftätern grundsätzlich keine bzw. keine unbegleiteten Ausgänge und Urlaube mehr zu bewilligen, sofern sie mit einer Ausweisung ernsthaft zu rechnen hätten. Ein solcher Schematismus verträgt sich mit dem Grundsatz der konkreten (und nicht abstrakten) Beurteilung der Fluchtgefahr nicht. <ref-law> trifft diesbezüglich denn auch keine Unterscheidung zwischen ausländischen und schweizerischen Straftätern, sondern gilt für alle Strafgefangenen in gleicher Weise (Urteil 6B_742/2010 vom 30. September 2010 E. 2.1). Dem Antrag des Ständerats anlässlich der Revision des Strafgesetzbuches, in einem Absatz 6bis festzuschreiben, dass "Gefangenen, gegen die eine ausländerrechtliche Fernhaltemassnahme verhängt wurde, in der Regel kein Urlaub gewährt" wird, war kein Erfolg beschieden (98.038; AB 1999 S 1132; AB 2001 N 589; AB 2002 S. 513). Ebenso wenig wird in <ref-law> eine Beschränkung des Vollzugsziels der Wiedereingliederung ausschliesslich in die schweizerische Gesellschaft statuiert. Soweit die Vorinstanz davon auszugehen scheint und "ein Interesse an einem ordnungsgemässen Abschluss des Strafvollzugs" nur für den Fall bejaht, dass ein Verbleib des ausländischen Gefangenen in der Schweiz mindestens wahrscheinlich erscheint (angefochtener Entscheid S. 6), ist ihre Auffassung mit Bundesrecht nicht vereinbar.
4.3 Selbst wenn eine Ausweisung des Beschwerdeführers ernsthaft in Betracht zu ziehen ist und davon ausgegangen werden darf, er werde die Schweiz nach der Strafverbüssung verlassen müssen, weshalb eine (gewisse) Fluchtgefahr ohne weiteres anzunehmen ist, müssen die konkreten Umstände eine Flucht nicht nur als möglich, sondern insgesamt als wahrscheinlich erscheinen lassen. Gegen die Annahme von Fluchtgefahr sprechen vorliegend entgegen der insoweit nicht nachvollziehbaren vorinstanzlichen Auffassung die dem Beschwerdeführer bislang bewilligten, problemlos verlaufenen 19 Beziehungsurlaube. Hätte der Beschwerdeführer fliehen wollen, hätte er seinen Entschluss bereits zahlreiche Male in die Tat umsetzen können. Er hat sich jedoch als vertragsfähig erwiesen, ist aus jedem Urlaub rechtzeitig in die Strafvollzugsanstalt zurückgekehrt und hat die ihm diesbezüglich auferlegten Bedingungen und Auflagen stets eingehalten (vgl. Ziff. 3 der Richtlinien der Ostschweizer Strafvollzugskommission über die Ausgangs- und Urlaubsgewährung vom 7. April 2006). Dabei wurde bereits im Rahmen der ersten Urlaubsgewährung vom 20. Mai 2009 das Risiko einer Flucht aufgrund der ernsthaft in Betracht zu ziehenden Ausweisung des Beschwerdeführers nach der Strafverbüssung von der zuständigen Behörde nicht verkannt, eine solche (Flucht-)Gefahr jedoch namentlich aufgrund des tragfähigen hiesigen Beziehungsnetzes des Beschwerdeführers, seiner familiären Bindungen und des regen Interesses an einem weiteren Verbleib in der Schweiz ausdrücklich verworfen (vgl. kantonale Akten, act. 4/3, Verfügung vom 20. Mai 2009). Dass und inwiefern sich diese Verhältnisse des Beschwerdeführers seither geändert haben bzw. die massgeblichen konkreten Umstände eine Flucht nunmehr neu geradezu als wahrscheinlich vermuten liessen, ergibt sich aus dem angefochtenen Entscheid indessen nicht und ist auch nicht ersichtlich. Das gilt umso mehr, als das Interesse des Beschwerdeführers, sich dem Strafvollzug durch Flucht zu entziehen, heute - d.h. relativ kurze Zeit vor einer möglichen bedingten Entlassung auf den 31. Januar 2013 - geringer ist als zu Beginn der Strafverbüssung, zumal er bei Flucht den Vollzug der ganzen Reststrafe von mehreren Jahren riskierte (vgl. auch St. Gallische Gerichts- und Verwaltungspraxis (GVP) 2010, Nr. 98, Urteil des Verwaltungsgerichts vom 15. April 2010, E. 2.6, S. 227). Weder mit diesem Gesichtspunkt noch mit dem weiteren Aspekt, wonach das öffentliche Interesse an einer Wiedereingliederung des Beschwerdeführers in die Gesellschaft heute gewichtiger erscheint als zu Beginn des ordentlichen Strafvollzugs (vgl. vorne E. 2.3) setzt sich die Vorinstanz auseinander. Sie stellt insoweit alleine auf das effektive Strafende im Jahre 2016 ab und erwägt, vor einem Entscheid über eine allfällig bedingte Entlassung sei davon auszugehen, dass der Beschwerdeführer noch eine längere Reststrafe zu verbüssen habe. Damit setzt die Vorinstanz sich über den Grundsatz hinweg, dass die bedingte Entlassung (worüber hier nicht zu befinden ist) die Regel bildet (<ref-ruling> E. 2.3) und deren zeitliche Nähe bei der Beurteilung der Fluchtgefahr in die Interessenabwägung im Rahmen von Gesuchen um Vollzugslockerungen einzubeziehen ist.
4.4 Zusammenfassend ergibt sich, dass die Vorinstanz die angeblich bestehende Fluchtgefahr nicht anhand der konkreten Umstände beurteilt bzw. nicht aufzeigt, inwiefern sich die bisherigen, gegen eine solche Gefahr sprechenden Verhältnisse des Beschwerdeführers geändert haben und eine Flucht nunmehr als wahrscheinlich erscheinen lassen. Die Vorinstanz lässt unter Hinweis auf die lange Freiheitsstrafe bzw. die theoretisch noch zu verbüssende Reststrafe im Ergebnis vielmehr die abstrakte Möglichkeit der Flucht genügen, wie sie an sich bei jedem ausländischen Straftäter besteht, der aufgrund seiner Delinquenz ernsthaft mit einer Ausweisung aus der Schweiz rechnen muss. Die Annahme von Fluchtgefahr im Sinne von <ref-law> beruht mithin auf einer einseitigen und abstrakten Betrachtungsweise und damit auf einer Ermessensverletzung durch die Vorinstanz. Die Beschwerde erweist sich als begründet. Die weiteren Rügen in Bezug auf die Verletzung von Art. 9, 10 und 29 Abs. 2 BV sowie von <ref-law> müssen nicht behandelt werden.
5. Die Beschwerde ist gutzuheissen, der angefochtene Entscheid aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
Bei diesem Ausgang des Verfahrens ist das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege gegenstandslos. Gerichtskosten entfallen. Der Kanton Zürich hat den Rechtsvertreter des Beschwerdeführers angemessen zu entschädigen (Art. 66 Abs. 4 und Art. 68 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 5. Juli 2011 aufgehoben und die Sache zur Neubeurteilung an die Vorinstanz zurückgewiesen.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
3. Es werden keine Gerichtskosten erhoben.
4. Der Kanton Zürich hat den Rechtsvertreter des Beschwerdeführers, Rechtsanwalt Dominik Ott, für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, und der Direktion der Justiz und des Innern des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 12. Januar 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill