Sachverhalt: A. Die Bezirksanwaltschaft Zürich erhob am 31. Mai 1990 gegen den italienischen Staatsangehörigen X._ Anklage wegen Verweisungsbruchs und Vergehens gegen das Bundesgesetz über Aufenthalt und Niederlassung der Ausländer (ANAG; in Kraft bis 31.12.2007). X._ wies 21 - mit einer Ausnahme einschlägige - Vorstrafen auf und war jeweils wegen Einreisens ohne gültigen Ausweis und/oder Missachtung der gegen ihn bestehenden Landesverweisung bestraft worden. Nach dem damaligen ärztlichen Gutachten stellten die zahlreichen illegalen Grenzüberschreitungen psychotische Handlungen dar, für welche er als unzurechnungsfähig angesehen werden musste. Das Bezirksgericht Zürich sprach ihn mit Urteil vom 11. Oktober 1990 wegen Schuldunfähigkeit von den Vorwürfen frei und wies ihn im Sinne von aArt. 43 Ziff. 1 Abs. 1 StGB in eine Pflegeanstalt ein. In der Folge hielt er sich bis Mitte des Jahres 2000 im Psychiatriezentrum Rheinau auf und trat danach in das Wohnheim Tilia über, wo er bis heute weilt. B. Das Amt für Justizvollzug des Kantons Zürich hob die stationäre Massnahme mit Verfügung vom 1. Juni 2010 wegen Aussichtslosigkeit auf. Dagegen rekurrierte X._ bei der Direktion der Justiz und des Innern (nachfolgend Justizdirektion) und beantragte in der Hauptsache die Fortführung der stationären Massnahme. Die Justizdirektion wies den Rekurs am 5. Oktober 2010 in der Hauptsache ab. Auf die von X._ erhobene Beschwerde trat das Verwaltungsgericht des Kantons Zürich mit Verfügung vom 13. Dezember 2010 nicht ein. C. Mit Beschwerde in Strafsachen beantragt X._, die Verfügung des Verwaltungsgerichts sei aufzuheben, und die Sache sei zur materiellen Prüfung und Entscheidung an die Vorinstanz zurückzuweisen. Zudem ersucht X._ um unentgeltliche Rechtspflege und Verbeiständung. Des Weiteren stellt er ein Gesuch um aufschiebende Wirkung, welches mit Präsidialverfügung vom 28. Februar 2011 gutgeheissen wurde. D. Das Verwaltungsgericht und das Amt für Justizvollzug beantragen in ihren Vernehmlassungen die Abweisung der Beschwerde.