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.