Sachverhalt: A. Das Bezirksgericht Zürich sprach X._ am 23. Juni 2006 der mehrfachen ungetreuen Geschäftsbesorgung, der mehrfachen Urkundenfälschung und der mehrfachen Fälschung von Ausweisen schuldig. Es verurteilte ihn zu drei Monaten Gefängnis als Zusatzstrafe zu der am 1. Februar 2005 mit Urteil der "Cour d'appel du Grand-Duché de Luxembourg" ausgesprochenen Gefängnisstrafe. Gleichzeitig ordnete das Bezirksgericht Zürich eine ambulante Massnahme im Sinne von aArt. 43 Ziff. 1 Abs. 1 StGB an. Das Amt für Justizvollzug des Kantons Zürich hob die Massnahme am 22. Oktober 2010 wegen Aussichtslosigkeit auf. B. Gegen die Aufhebung der ambulanten Massnahme rekurrierte X._ bei der Justizdirektion des Kantons Zürich und erhob gegen deren ablehnende Verfügung Beschwerde beim Verwaltungsgericht des Kantons Zürich, welches diese am 17. August 2011 teilweise guthiess. Es hob die Verfügung des Amtes für Justizvollzug des Kantons Zürich vom 22. Oktober 2011 (recte: 2010) auf und wies die Sache im Sinne der Erwägungen an dieses zurück (Disp.-Ziff. 2). Es nahm die Kosten auf die Gerichtskasse (Disp.-Ziff. 3). Eine Parteientschädigung sprach es X._ nicht zu (Disp.-Ziff. 4). Am 30. September 2011 verfügte das Amt für Justizvollzug des Kantons Zürich die Weiterführung der ambulanten Massnahme. C. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, Disp.-Ziff. 4 des Urteils des Verwaltungsgerichts des Kantons Zürich aufzuheben und ihm für das verwaltungsgerichtliche Verfahren eine Parteientschädigung im Umfang von Fr. 4'553.40 (inkl. MWST), zahlbar an seine Rechtsvertreterin, zuzusprechen. Eventualiter sei Disp.-Ziff. 4 des Urteils des Verwaltungsgerichts des Kantons Zürich aufzuheben und die Sache an die Vorinstanz zurückzuweisen. Ausserdem sei für das bundesgerichtliche Verfahren die unentgeltliche Prozessführung und Verbeiständung zu bewilligen. D. Das Verwaltungsgericht des Kantons Zürich beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten ist. Das Amt für Justizvollzug des Kantons Zürich verzichtet auf eine Vernehmlassung.