Sachverhalt: A. A.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. A._ wurde namentlich 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. A.b. Das Bundesverwaltungsgericht bestätigte mit Urteil E-1249/2012 am 28. Oktober 2013 den Widerruf des Asyls durch das Staatssekretariat für Migration (SEM). Mit Amtsbericht vom 20. Februar 2013 teilte das SEM den zürcherischen Behörden mit, der Vollzug der Wegweisung sei zulässig. Daraufhin widerrief das Migrationsamt des Kantons Zürich am 9. Oktober 2015 die Niederlassungsbewilligung von A._. Den Widerruf bestätigte die Sicherheitsdirektion des Kantons Zürich. Auf eine gegen deren Rekursentscheid vom 23. November 2015 erhobene Beschwerde trat das Verwaltungsgericht des Kantons Zürich infolge Nichtleistung des Kostenvorschusses nicht ein. Eine gegen den Nichteintretensentscheid des Verwaltungsgerichts vom 20. Januar 2016 geführte Beschwerde ist beim Bundesgericht hängig (Verfahren 2C_139/2016). B. Am 26. November 2015 verfügte das Migrationsamt die Überführung von A._ vom Strafvollzug in die Ausschaffungshaft bis zum 2. März 2016 zwecks Sicherstellung des Wegweisungsvollzugs. Am 3. Dezember 2015 wurde die angeordnete Ausschaffungshaft angetreten. Das Zwangsmassnahmengericht des Bezirksgerichts Zürich bestätigte die Rechtmässigkeit der angeordneten Ausschaffungshaft am 4. Dezember 2015. Hiergegen erhob A._ am 22. Dezember 2015 (eingegangen am 29. Dezember 2015) Beschwerde an das Verwaltungsgericht des Kantons Zürich und beantragte sinngemäss die Bestellung eines unentgeltlichen Rechtsbeistands sowie die sofortige Haftentlassung und eine Entschädigung infolge unrechtmässig verbüsster Haft. Mit Präsidialverfügung vom 29. Dezember 2015 wurde er darauf hingewiesen, dass es ihm obliege, bei Bedarf einen Rechtsvertreter zu beauftragen. Mit Eingabe vom 11. Januar 2016 ersuchte A._ zur Hauptsache erneut um sofortige Haftentlassung. Mit Schreiben vom 17. Januar 2016 ersuchte er wieder um amtliche Bestellung eines unentgeltlichen Rechtsanwalts. Das Verwaltungsgericht hat die Eingaben vom 22. Dezember 2015 und vom 11. Januar 2016 vereinigt und mit Urteil vom 19. Januar 2016 abgewiesen. C. Mit Eingabe vom 30. Januar 2016 beantragt A._ dem Bundesgericht, es sei ihm ein unentgeltlicher Pflichtverteidiger beizugeben. Sodann sei er aus der Haft zu entlassen. Schliesslich sei ihm eine Entschädigung für die erstandene Haft auszurichten. Das Verwaltungsgericht des Kantons Zürich beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das SEM beantragt, die Beschwerde sei abzuweisen. Der Beschwerdeführer hält sinngemäss an seinen Anträgen fest.