Sachverhalt: A. A._, 1985 geborener Staatsangehöriger von Somalia, reiste am 2. Mai 1995 zusammen mit seiner Mutter in die Schweiz ein. Das damalige Bundesamt für Flüchtlinge (BFF; heute: Staatssekretariat für Migration SEM) verfügte am 29. September 1995 die Wegweisung der Familie aus der Schweiz, lehnte das Asylgesuch ab und ordnete die vorläufige Aufnahme an. Am 3. Juni 2009 hob das Bundesamt für Migration (heute SEM) die vorläufige Aufnahme von A._ auf und wies ihn aus der Schweiz weg. Auf eine hiergegen erhobene Beschwerde trat das Bundesverwaltungsgericht am 28. Juni 2009 nicht ein. Mit Urteil des Obergerichts des Kantons Bern vom 25. März 2011 wurde A._ wegen versuchter Tötung, mehrfach versuchter schwerer Körperverletzung und weiterer Delikte namentlich im Betäubungsmittelbereich zu einer Freiheitsstrafe von sechs Jahren verurteilt. Die Abteilung Straf- und Massnahmenvollzug im Amt für Freiheitsentzug lehnte die bedingte Entlassung am 10. Juli 2013 ab. A._ verbüsste seine Strafe bis zum ordentlichen Strafende am 12. September 2015. B. Mit Verfügung vom 14. September 2015 ordnete das Migrationsamt des Kantons Solothurn die Durchsetzungshaft per Strafende für einen Monat an. Das Haftgericht genehmigte mit Entscheid vom 16. September 2015 die angeordnete Durchsetzungshaft bis zum 11. Oktober 2015. Am 13. Oktober 2015 genehmige das Haftgericht die vom Migrationsamt beantragte Haftverlängerung bis zum 10. Dezember 2015. Die gegen die Haftbestätigungsentscheide beim Verwaltungsgericht des Kantons Solothurn erhobenen Beschwerden wurden vereinigt und am 16. November 2015 abgewiesen. C. Mit Beschwerde vom 29. Dezember 2015 beantragt A._ dem Bundesgericht, den Entscheid vom 16. November 2015 aufzuheben; er sei umgehend aus der Durchsetzungshaft zu entlassen. Der Beschwerdeführer verlangt eine Genugtuung für die seit dem 12. September 2015 ausgestandene Überhaft in der Höhe von mindestens Fr. 100.-- pro Tag. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung. Das Migrationsamt und das Verwaltungsgericht des Kantons Solothurn beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Haftgericht verzichtet auf eine Vernehmlassung. Das Staatssekretariat führt in seiner Stellungnahme aus, eine Rückkehr nach Somalia sei nur bei freiwilliger Ausreise möglich. Der Beschwerdeführer hält in einer weiteren Eingabe vom 21. Januar 2016 an seinen Anträgen fest.