Sachverhalt: A. A._ (geb. 1965) stammt aus Afghanistan. Er reiste 1986 in die Schweiz ein, wurde rund drei Jahre später als Flüchtling anerkannt und erhielt die Niederlassungsbewilligung. Während seiner Anwesenheit in der Schweiz gab A._ mehrfach zu teils schweren Klagen Anlass. Namentlich wurde er am 8. November 2000 vom Bezirksgericht U._ wegen sexueller Nötigung, sexuellen Handlungen mit einem Kind sowie versuchter Nötigung zu einer Gefängnisstrafe von sechzehn Monaten verurteilt. Am 9. Juli 2010 erfolgte durch das Obergericht Zürich eine weitere Verurteilung wegen mehrfacher Vergewaltigung, mehrfacher sexueller Nötigung, mehrfachen sexuellen Handlungen mit Kindern sowie Pornographie zu einer Freiheitsstrafe von acht Jahren. Unter Anrechnung von 948 Tagen bereits erstandenen Freiheitsentzugs trat A._ gleichentags den Strafvollzug an. B. B.a. Im Hinblick auf den geplanten Widerruf der Niederlassungsbewilligung und die Wegweisung aus der Schweiz wurde A._ am 23. Dezember 2013 und erneut am 23. September 2015 das rechtliche Gehör gewährt. Mit Verfügung vom 9. Oktober 2015 widerrief das Migrationsamt des Kantons Zürich schliesslich die Niederlassungsbewilligung von A._ und wies ihn aus der Schweiz weg. Einen dagegen gerichteten Rekurs wies die Sicherheitsdirektion des Kantons Zürich mit Entscheid vom 23. November 2015 ab. B.b. Auf das Ende des Strafvollzugs am 3. Dezember 2015 ordnete das Migrationsamt mit Verfügung vom 25. November 2015 die Überführung von A._ in die Ausschaffungshaft an. Die Ausschaffungshaft und ihre Verlängerung wurde gerichtlich jeweils bestätigt, zuletzt bis 2. Juni 2016 (vgl. hierzu auch Urteile 2C_516/2016 vom 1. Juni 2016; 2C_450/2016 vom 27. Mai 2016; 2C_313/2016 vom 13. April 2016; 2C_112/2016 vom 19. Februar 2016). B.c. Gegen den Rekursentscheid der Sicherheitsdirektion vom 23. November 2015 gelangte A._ mit Eingabe vom 30. November 2015 an das Verwaltungsgericht des Kantons Zürich (Postaufgabe: 1. Dezember 2015; Eingang beim Verwaltungsgericht: 2. Dezember 2015). Dabei beantragte er, dass ihm die Niederlassungsbewilligung zu belassen und auf eine Wegweisung zu verzichten sei. Ausserdem ersuchte er um unentgeltliche Rechtspflege und Beigabe eines unentgeltlichen Rechtsbeistands. Auf seiner Beschwerde vermerkte A._ die Adresse der Justizvollzugsanstalt Pöschwies, wo er sich damals noch im Strafvollzug befand. Das Verwaltungsgericht wies das Gesuch um unentgeltliche Rechtspflege mit Verfügung des Abteilungspräsidenten vom 2. Dezember 2015 ab. Zugleich setzte es eine nicht erstreckbare Frist von 20 Tagen für die Bezahlung eines Gerichtskostenvorschusses von Fr. 2'060.-- an. Der Versuch einer Zustellung der Verfügung am 3. Dezember 2015 an A._ in der Justizvollzugsanstalt Pöschwies scheiterte; er wurde gleichentags in die Ausschaffungshaft überführt. Die Verfügung vom 2. Dezember 2015 wurde dem Verwaltungsgericht mit dem Vermerk "Empfänger konnte unter angegebener Adresse nicht ermittelt werden" wieder retourniert. A._ teilte dem Verwaltungsgericht mit Schreiben vom 13. Dezember 2016 (Postaufgabe: 14. Dezember 2016) seine neue Zustelladresse im Flughafengefängnis Zürich mit. Auf die Beschwerde vom 30. November 2015 trat das Verwaltungsgericht alsdann mit Verfügung vom 20. Januar 2016 nicht ein, weil der mit Verfügung vom 2. Dezember 2015 verlangte Kostenvorschuss nicht geleistet worden war. C. Gegen den Nichteintretensentscheid des Verwaltungsgerichts vom 20. Januar 2016 gelangt A._ mit Beschwerde vom 7. Februar 2016 an das Bundesgericht. Er verlangt sinngemäss die Aufhebung des angefochtenen Entscheids sowie die Erteilung der unentgeltlichen Rechtspflege und die Beigabe eines kostenlosen Rechtsbeistands. Das Verwaltungsgericht und das SEM beantragen die Abweisung der Beschwerde. Mit Stellungnahme vom 2. Juni 2016 hält der Beschwerdeführer an seinen Anträgen und der Begründung fest.