Sachverhalt:
A.
A._ (1992; Iraker; bis 4. August 2016 Flüchtling [Nichteintretensentscheid des Bundesverwaltungsgerichts vom 22. September 2016 auf die Beschwerde gegen den Asylwiderruf und gegen die Aberkennung der Flüchtlingseigenschaft des SEM vom 4. August 2016 (Eröffnung 5. August 2016)]) ist im Jahr 1999 zusammen mit seinem Vater und einem Bruder in die Schweiz eingereist. Nachdem jener als Flüchtling anerkannt und ihm Asyl gewährt worden war, wurde A._ im Jahr 2000 gemäss <ref-law> (SR 142.31) als Flüchtling anerkannt, und es wurde ihm Familienasyl gewährt. Am 27. September 2004 hat A._ eine Niederlassungsbewilligung erhalten. Im Juli 2014 ist er in den Irak gereist, um bei seinen Eltern in U._ Ferien zu verbringen. Am 21. August 2014 ist ihm dort ein irakischer Reisepass ausgestellt worden. Am 30. August 2014 ist er aus dem Irak aus- und in die Schweiz eingereist. Am 4. Februar 2015 wurde ihm in der Schweiz ein Reiseausweis für Flüchtlinge ausgestellt. Am 5. Juni 2015 ist er für Ferien bei seiner Familie und zum Heiraten in den Irak eingereist. Nachdem die Hochzeit nicht zustande gekommen sei, sei er in den Iran gereist, um dort etwas herumzureisen und sich zu beruhigen. Nach einem dreitägigen Aufenthalt im Iran sei er beim Versuch, wieder in den Irak auszureisen, an der Grenze festgenommen und ein Jahr lang in Haft gehalten worden. Nach seiner Freilassung sei er in den Irak zurückgekehrt. Am 12. Juli 2016 ist A._ aus dem Irak aus- und am 13. Juli 2016 in die Schweiz eingereist.
B.
Mit Verfügung vom 5. Juli 2016 (Eröffnung: 14. Juli 2016) hat das Staatssekretariat für Migration (SEM) ein ab sofort bis am 19. September 2016 gültiges Einreiseverbot gegen A._ erlassen und einer allfälligen Beschwerde dagegen die aufschiebende Wirkung entzogen. Mit Verfügung vom 15. Juli 2016 hat das Migrationsamt des Kantons Basel-Stadt (nachfolgend: Migrationsamt) sodann A._ aus der Schweiz weggewiesen und die sofortige Vollstreckung der Wegweisung angeordnet. Dagegen hat dieser am 18. Juli 2016 beim Justiz- und Sicherheitsdepartement Rekurs erhoben und gleichentags, aber separat, die Gewährung der aufschiebenden Wirkung beantragt.
C.
Die Einzelrichterin für Zwangsmassnahmen im Ausländerrecht hat mit Urteil vom 18. Juli 2016 die Ausschaffungshaft für A._ zunächst für die Dauer von 16 Tagen und am 29. Juli 2016 bis am 29. Oktober 2016 bewilligt. Gestützt auf die Hinweise des Migrationsamtes hat das SEM am 4. August 2016 diesem sodann die Flüchtlingseigenschaft aberkannt und das Asyl widerrufen, da er mit seinen Reisen in den Irak und der Annahme dessen Reisepasses sich freiwillig unter den Schutz seines Heimatlandes gestellt habe. Dieser Entscheid ist nun, d.h. nach Erhebung der Beschwerde ans Bundesgericht, in Rechtskraft erwachsen (siehe oben lit. A).
D.
Das Justiz- und Sicherheitsdepartement hat mit Zwischenentscheid vom 21. Juli 2016 den Antrag auf Gewährung der aufschiebenden Wirkung des Rekurses gegen die Wegweisungsverfügung abgewiesen; gleichzeitig hat es angeordnet, dass A._ bis 22. August 2016 einen Kostenvorschuss von CHF 500.-- für das verwaltungsinterne Rekursverfahren zu leisten habe, ansonsten der Rekurs abgeschrieben werde. Dagegen hat A._ beim Regierungsrat Rekurs angemeldet und u.a. Gewährung der aufschiebenden Wirkung beantragt. Das Präsidialdepartement hat den Rekurs am 28. Juli 2016 dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht zum Entscheid überwiesen. Dieses hat mit Entscheid vom 12. August 2016 den Rekurs in Bezug auf die Gewährung der aufschiebenden Wirkung abgewiesen und den Entscheid über die weiteren Anträge für später vorgesehen.
E.
Vor Bundesgericht beantragt A._, den Entscheid des Appellationsgerichts des Kanton Basel-Stadt aufzuheben und die aufschiebende Wirkung des Rekurses gegen die Wegweisungsverfügung vom 15. Juli 2016 wiederherzustellen. Zudem beantragt er unentgeltliche Rechtspflege.
F.
Das Appellationsgericht, das Migrationsamt und das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt beantragen die Abweisung der Beschwerde. Das SEM liess sich ohne Antrag ausführlich vernehmen. Der Beschwerdeführer repliziert. Am 15. September 2016 wurde der Beschwerde superprovisorisch aufschiebende Wirkung zuerkannt.

Erwägungen:
1.
1.1. Streitgegenstand des vorliegenden Verfahrens bildet lediglich die Frage, ob die aufschiebende Wirkung, welche der Beschwerde gegen die in casu erlassene Wegweisungsverfügung nach Art. 64 Abs. 1 lit. b AuG (SR 142.20) nicht zukommt (Art. 64 Abs. 3 Satz 2 AuG), wiederherzustellen ist (vgl. Art. 64 Abs. 3 Satz 3 AuG). Selbständig eröffnete Entscheide über Gesuche um vorsorgliche Massnahmen beenden das Verfahren nicht (vgl. <ref-law>) und sind somit Zwischenentscheide im Sinne von <ref-law> (vgl. <ref-ruling> E. 2.1 S. 606). Eine Beschwerde gegen Zwischenentscheide steht nur offen, wenn der Entscheid in der Hauptsache der Beschwerde an das Bundesgericht unterliegt. Fällt eine Streitsache in den Anwendungsbereich einer Ausnahmeregelung von <ref-law>, kann kein in dieser Sache ergangener Zwischenentscheid beim Bundesgericht mit öffentlich-rechtlicher Beschwerde nach <ref-law> angefochten werden. Dies trifft im vorliegenden Fall zu: Streitgegenstand im Hauptverfahren bildet die Frage der Zulässigkeit der Wegweisungsverfügung, gegen welche nach Art. 83 lit. c Ziff. 4 i.f. BGG die Beschwerde unzulässig ist.
1.2. Die subsidiäre Verfassungsbeschwerde nach <ref-law> ist hingegen in der Hauptsache zulässig, da der Beschwerdeführer - auch wenn er zwar die falsche Bezeichnung, in der Sache allerdings die korrekten formellen Voraussetzungen des Rechtsmittels verwendet hat (<ref-ruling> E. 3.1 S. 499 mit Hinweisen) - durch die Anrufung einer Verletzung von Art. 3 EMRK, von Art. 3 Abs. 1 des Übereinkommens vom 10. Dezember 1984 gegen Folter und andere grausame, unmenschliche oder erniedrigende Behandlung oder Strafe (FoK; SR 0.105) sowie von Art. 33 Abs. 1 des Abkommens vom 28. Juli 1951 über die Rechtsstellung der Flüchtlinge (GFK; SR 0.142.30) [korrekterweise i.V.m. Art. I des Protokolls vom 31. Januar 1967 über die Rechtsstellung der Flüchtlinge (PGFK; SR 0.142.301)], die <ref-law> entsprechen, ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids in der Hauptsache hat (vgl. <ref-ruling> E. 1.2 S. 290; <ref-ruling> E. 3.2 S. 235; <ref-ruling> E. 1.3 S. 269 f.). Insofern sind auch Beschwerden gegen Zwischenentscheide zulässig, wenn sie die Voraussetzungen des hier anwendbaren <ref-law> und weitere Voraussetzungen erfüllen (vgl. <ref-law>).
1.3. Gegen selbständig eröffnete Zwischenentscheide, die weder die Zuständigkeit noch den Ausstand betreffen (<ref-law>), ist die Beschwerde nur zulässig, wenn diese einen nicht wieder gutzumachenden Nachteil bewirken können (<ref-law>) oder die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (<ref-law>). Dabei sind die Voraussetzungen nach <ref-law> vom Beschwerdeführer darzulegen (<ref-ruling> E. 1.1 S. 328 f.; <ref-ruling> E. 1.2 S. 429), soweit sie nicht offensichtlich erfüllt sind (<ref-ruling> E. 4 S. 95 f.; <ref-ruling> E. 2.3.1 S. 632). Dieser macht geltend, dass ihm - nach dem grossen Medienecho nach dem Entscheid der Vorinstanz, wo er als Terrorist und Jihadist bezeichnet wurde - bei einer Rückschiebung in den Irak Gefängnis, Folter und unmenschliche Behandlung drohen würden. Insofern ist die angefochtene Verfügung geeignet, einen nicht wieder gutzumachenden Nachteil bewirken zu können. <ref-law> ist somit erfüllt. Der Beschwerdeführer ist als Adressat des vorliegenden Zwischenentscheids formell beschwert und er hat auch ein rechtlich geschütztes Interesse an dessen Überprüfung auf Übereinstimmung mit Art. 3 i.V.m. Art. 13 EMRK, Art. 3 FoK und Art. 33 GFK i.V.m. Art. I PGFK. Die Beschwerde ist frist- und formgerecht (Art. 117 i.V.m. <ref-law>).
1.4. Im Rahmen der subsidiären Verfassungsbeschwerde kann nur eine Verletzung verfassungsmässiger Rechte gerügt werden, welche präzise und qualifiziert begründet werden muss (vgl. Art. 116 i.V.m. Art. 117 i.V.m. Art. 106 Abs. 2 bzw. hier auch Art. 98 i.V.m. <ref-law>). Der Beschwerdeführer bringt genügend klar und detailliert vor, dass die Verweigerung der Wiederherstellung der aufschiebenden Wirkung und die damit ohne vertiefte Prüfung verbundene Wegweisung Art. 3 i.V.m. Art. 13 EMRK, Art. 3 FoK und Art. 33 GFK i.V.m. Art. I PGFK verletze.
1.5. Das Bundesgericht legt seinem Urteil sodann den Sachverhalt zu Grunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). In der Beschwerdeschrift ist darzulegen, dass die Vorinstanz den Sachverhalt unter Verletzung verfassungsmässiger Rechte (<ref-law> i.V.m. <ref-law>) nicht oder unrichtig festgestellt hat. Neben der Erheblichkeit der gerügten Tatsachenfeststellung für den Ausgang des Verfahrens ist klar und detailliert darzutun, inwiefern diese verfassungswidrig, insbesondere willkürlich (<ref-law>), d.h. mit der tatsächlichen Situation in klarem Widerspruch stehe, auf einem offenkundigen Versehen beruhe oder sich sachlich in keiner Weise rechtfertigen lasse (<ref-ruling> E. 7.1 S. 398). In die vorinstanzliche Beweiswürdigung greift das Bundesgericht nur ein, wenn diese willkürlich ist (<ref-ruling> E. 2.1 S. 9; Urteil 4A_56/2013 vom 4. Juni 2013 E. 2). Die Sachverhaltsfeststellung bzw. Beweiswürdigung erweist sich als willkürlich (<ref-law>), wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt hat, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat. Dass die von Sachgerichten gezogenen Schlüsse nicht mit der eigenen Darstellung des Beschwerdeführers übereinstimmen, belegt keine Willkür (<ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 4.2 S. 560).
Der Beschwerdeführer macht in einer Überschrift geltend, dass der Sachverhalt willkürlich festgestellt worden sei. Im Text selber führt er aus, dass seine unterschiedlichen Angaben sehr wohl plausibel erklärt werden können und genügend klar und in sich logisch seien, sodass seinen Angaben betreffend konkrete Gefährdung geglaubt werden müsse. Bei den einzelnen Sachverhaltselementen führt er diesbezüglich aus, dass seine Aussagen nicht widersprüchlich seien, weil er später seine Aussagen präzisiert, sich wieder erinnert oder bei einer späteren Aussage korrigiert habe. Insofern seien diese durchaus widerspruchslos und logisch nachvollziehbar. Damit zeigt der Beschwerdeführer indes in keiner Weise, dass die Tatsachenfeststellung mit der tatsächlichen Situation in klarem Widerspruch stehe, auf einem offenkundigen Versehen beruhe oder sich sachlich in keiner Weise rechtfertigen lasse. Er stellt dabei lediglich seine Aussagen etwas anders dar; im Kern bleiben die Aussagen indes die gleichen.
2.
2.1. Der Beschwerdeführer hat die Schweiz verlassen, ohne sich abzumelden, weshalb seine Niederlassungsbewilligung nach Art. 61 Abs. 2 AuG nach sechs Monaten erloschen ist. Dies trifft auch bei unfreiwilligem Verweilen im Ausland zu (vgl. Urteil 2C_461/2012 vom 7. November 2012 E. 4.2.1; MARC SPESCHA, in: Spescha/Thür/Zünd/ Bolzli/Hruschka (Hrsg.), Migrationsrecht, Kommentar, 4. Aufl. 2015, Art. 61 N. 5). Wegen fehlenden gültigen Reisedokumenten erfüllte der Beschwerdeführer die Einreisevoraussetzungen von Art. 5 Abs. 1 lit. a AuG i.V.m. Art. 4 und 5 VEV (SR 142.204) nicht mehr. In der Folge erliess das Migrationsamt des Kantons Basel-Stadt gestützt auf Art. 64 Abs. 1 lit. b AuG eine ordentliche Wegweisungsverfügung. Nach Art. 64 Abs. 3 kommt der Beschwerde von Gesetzes wegen keine aufschiebende Wirkung zu; allerdings kann die Beschwerdeinstanz über deren Wiederherstellung befinden. Ob die Vorinstanzen zu Recht davon abgesehen haben, bildet Streitgegenstand des vorliegenden Verfahrens.
2.2. Der Entscheid über die Wiederherstellung der aufschiebenden Wirkung hat sich an denselben Kriterien wie deren Entzug zu orientieren (vgl. HANSJÖRG SEILER, in: Waldmann/Weissenberger [Hrsg.], Praxiskommentar Verwaltungsverfahrensgesetz, 2. Aufl. 2016, Art. 55 N. 150; REGINA KIENER, in: Auer/Müller/Schindler [Hrsg.]), VwVG Kommentar, 2008, Art. 55 N. 14). Ob im Einzelfall der Entzug der aufschiebenden Wirkung zu belassen oder diese wiederherzustellen ist, beurteilt sich aufgrund einer Interessenabwägung. Es ist zu prüfen, ob die Gründe, welche für die sofortige Vollstreckbarkeit der Verfügung sprechen, gewichtiger sind als jene, die für die gegenteilige Lösung angeführt werden können (<ref-ruling> E. 3 S. 289; Urteil 2C_293/2013 vom 21. Juni 2013 E. 4.1, nicht publiziert in <ref-ruling>; FRITZ GYGI, Bundesverwaltungsrechtspflege, 2. Aufl. 1983, S. 244). Einerseits soll der Beschwerdeführer vor der Überprüfung der Rechtmässigkeit der angefochtenen Verfügung vor deren nachteiligen Folgen geschützt bleiben, wäre doch sonst der Rechtsschutz illusorisch. Andererseits besteht auch ein schutzwürdiges Interesse daran, dass der mit dem Gesetz bzw. der Verfügung angestrebte Zweck noch erreicht werden kann und nicht durch ein langes Verfahren mit Suspensiveffekt hintertrieben wird (vgl. <ref-ruling> E. 3.2 S. 290; PIERRE MOOR/ETIENNE POLTIER, Droit administratif. Vol. II. Les actes administratifs et leur contrôle, 2011, S. 307; SEILER, a.a.O., Art. 55 N. 93). Bei der Wegweisungsverfügung hat das AuG den Entzug der aufschiebenden Wirkung als Grundsatz vorgesehen, deren Wiederherstellung als Ausnahme. Dies bedeutet indes nicht, dass nur ganz aussergewöhnliche Gründe die Wiederherstellung rechtfertigen könnten (vgl. <ref-ruling> E. 3.2 S. 290 für den umgekehrten Fall). Massgebend ist lediglich, dass die Gründe derart gewichtig sind, dass sie die Interessen für die Beibehaltung des gesetzlich vorgesehenen Entzugs überwiegen. Es ist folglich abzuwägen, ob dem Staat bzw. dem Beschwerdeführer der durch den Schwebezustand verursachte Nachteil am ehesten zugemutet werden kann; dabei sind die Schwere des drohenden Nachteils wie auch die Wahrscheinlichkeit seines Eintretens zu würdigen und auch die voraussichtliche Dauer des Schwebezustands zu berücksichtigen (vgl. SEILER, a.a.O., Art. 55 N. 96 m.H.; ISABELLE HÄNER, Vorsorgliche Massnahmen im Verwaltungsverfahren und Verwaltungsprozess, ZSR 1997 II 253 ff., 332 ff., insbes. 335 ff., Rz. 105 ff.; KIENER, a.a.O., Art. 55 N. 14 ff.). Je schwerer der Eingriff für den Beschwerdeführer ist, umso eher liegen Gründe für die Wiederherstellung der aufschiebenden Wirkung vor (vgl. Urteil 2C_575/2014 vom 28. Juli 2014 E. 2.1).
Mit dem gesetzlich vorgesehenen Entzug der aufschiebenden Wirkung wird die Wegweisungsverfügung vorzeitig vollstreckbar und schafft für die Dauer des vorinstanzlichen Beschwerdeverfahrens einen gerichtlich noch nicht überprüften und damit möglicherweise rechtswidrigen Zustand (vgl. Urteil 2C_575/2014 vom 28. Juli 2014 E. 2.2). Irreparable Nachteile und präjudizierende Wirkungen sind deshalb zu vermeiden, das Ergebnis des Hauptverfahrens soll weder verunmöglicht noch unwiderruflich zementiert werden (vgl. <ref-ruling> E. 2.2 S. 155).
Bei der Interessenabwägung kommt der Vorinstanz ein erheblicher Beurteilungsspielraum zu. In diesen greift das Bundesgericht nur ein, wenn sie wesentliche Interessen falsch bewertet oder ausser Acht gelassen hat oder den Sachentscheid in unzulässiger Weise präjudiziert und damit im Ergebnis Bundesrecht vereitelt (<ref-ruling> E. 3 S. 289; Urteile 2C_575/2014 vom 28. Juli 2014 E. 2.1; 1C_88/2009 vom 31. August 2009 E. 3.1).
2.3. Mit der gesetzlichen Regelung von Art. 64 Abs. 3 Satz 2 AuG, wonach der Beschwerde keine aufschiebende Wirkung zukommt, soll der mit dem Gesetz bzw. der Verfügung angestrebte Zweck noch erreicht werden und nicht durch ein langes Verfahren mit Suspensiveffekt hintertrieben werden. Verstärkt wird diese Intention bei besonderen Konstellationen, welche in Art. 64d Abs. 2 AuG aufgeführt sind: So ist die Wegweisung sofort vollstreckbar oder es kann eine Ausreisefrist von weniger als sieben Tagen angesetzt werden, wenn die betroffene Person eine Gefahr für die öffentliche Sicherheit und Ordnung oder die innere oder die äussere Sicherheit darstellt (lit. a) oder konkrete Anzeichen befürchten lassen, dass sich die betroffene Person der Ausschaffung entziehen will (lit. b). Die Vorinstanz hat im Hinblick auf die Anwendung von <ref-law> (dazu <ref-ruling> E. 5.4 S. 73 f.; <ref-ruling> E. 2.2.2 S. 114 m.H.; Urteil 2D_3/2012 vom 2. August 2012 E. 3) sich mit den beiden Artikeln auseinandergesetzt und gestützt auf die Berichte des SEM und des Nachrichtendienstes des Bundes (vgl. Art. 67 Abs. 4 AuG) festgehalten, dass die beiden Bestimmungen erfüllt sind. Der zugrundeliegende Sachverhalt ist - wie bereits dargelegt - nicht willkürlich festgestellt. Die Rechtsanwendung hat der Beschwerdeführer nicht gerügt. Es ist auch kein Grund ersichtlich, inwiefern diese falsch sein sollte. Nachdem das Bundesverwaltungsgericht am 22. September 2016 auf die Beschwerde gegen den Asylwiderruf des SEM vom 4. August 2016 nicht eingetreten und dieser nun rechtskräftig ist, ist <ref-law> und die Ausnahme davon in <ref-law> nicht mehr anwendbar.
2.4. Der Beschwerdeführer rügt indes Art. 3 i.V.m. Art. 13 EMRK, <ref-law>, Art. 3 FoK und Art. 33 GFK i.V.m. Art. I PGFK. Art. 3 EMRK stellt ein absolutes Recht dar; keine noch so gewichtigen gegenläufigen Interessen können einen Verstoss gegen Art. 3 EMRK rechtfertigen; eine Interessenabwägung ist unzulässig (vgl. Urteil des EGMR Gäfgen gegen Deutschland vom 1. Oktober 2010, Nr. 22978/05, § 87; Chahal gegen Grossbritannien vom 15. November 1996, Nr. 22414/93, § 78 f.; A. gegen die Niederlande vom 20. Juli 2010, Nr. 4900/06, § 143; BGE <ref-ruling> E. 2.2.2 S. 114 m.H.; siehe auch CHRISTOPH GRABENWARTER/KATHARINA PABEL, Europäische Menschenrechtskonvention. Ein Studienbuch, 6. Aufl. 2016, § 20 N. 51, 87; ANNE PETERS/TILMANN ALTWICKER, Europäische Menschenrechtskonvention, 2. Aufl. 2012, § 6 N. 3; STEFAN SINNER, in: Karpenstein/Mayer, EMRK, Kommentar, 2. Aufl. 2015, Art. 3 N. 4; JENS MEYER-LADEWIG, EMRK, Handkommentar, 3. Auf. 2011, Art. 3 N. 2 ff., 63; RALPH ALEXANDER LORZ/HEIKO SAUER, Wann genau steht Art. 3 EMRK einer Auslieferung oder Ausweisung entgegen?, EuGRZ 2010, S. 389 ff., 392; MARTINA CARONI/TOBIAS GRASDORF-MEYER/LISA OTT/ NICOLE SCHREIBER, Migrationsrecht, 3. Aufl. 2014, S. 51). Insofern kann Art. 3 EMRK die bei der Beurteilung vorsorglicher Massnahmen vorgesehene Interessenabwägung übersteuern (vgl. BGE <ref-ruling> E. 3.2 S. 117) : Bei einer drohenden Verletzung von Art. 3 EMRK kommt es deshalb zu keiner Interessenabwägung, selbst bei terroristischen Bedrohungen des Aufnahmestaates durch die wegzuschaffende Person, wie der EGMR - auch wenn ihm die schwierige Situation wie im Übrigen auch bei der Migration (vgl. Urteil des EGMR Hirsi Jamaa gegen Italien vom 23. Februar 2012, Nr. 27765/09, § 122) bewusst ist - immer wieder betonte (vgl. etwa Urteil des EGMR A. gegen die Niederlande vom 20. Juli 2010, Nr. 4900/06, § 143; Daoudi gegen Frankreich vom 3. Dezember 2009, Nr. 19576/80, § 65; GRABENWARTER/ PABEL, a.a.O., § 20 N. 40, 87).
3.
3.1. Nach der Europäische Menschenrechtskonvention haben die Mitgliedstaaten das Recht, die Einreise, den Aufenthalt und die Aufenthaltsbeendigung, insbesondere die Wegweisung und Ausweisung von Ausländern zu regeln (vgl. <ref-ruling> E. 2 S. 335 ff.; Urteil des EGMR Hirsi Jamaa gegen Italien vom 23. Februar 2012, Nr. 27765/09, § 113). Aufenthaltsbeendende Massnahmen können aber Art. 3 EMRK-relevant werden und die Verantwortlichkeit des Mitgliedstaates begründen, wenn es nachweisbar ernsthafte Gründe dafür gibt, dass der Betroffene im Falle der Wegweisung tatsächlich Gefahr läuft, im Aufnahmeland einer Behandlung ausgesetzt zu werden, die gegen Art. 3 EMRK verstösst. Verboten ist deshalb namentlich, eine Person in einen Staat zu verbringen, in dem sie konkret und ernsthaft Gefahr läuft ("real risk"), der Folter oder unmenschlicher bzw. erniedrigender Behandlung ausgesetzt zu sein (vgl. Urteil 2C_532/2015 vom 23. Dezember 2015 E. 2.4.1; 2C_1130/2013 vom 23. Januar 2015 E. 2.2.; Urteil des EGMR Hirsi Jamaa gegen Italien vom 23. Februar 2012, Nr. 27765/09, § 114; GRABENWARTER/PABEL, a.a.O., § 20 N. 75, 78). Dabei obliegt dem Beschwerdeführer, die für ihn günstigen Tatsachen zu beweisen (vgl. Urteil 2C_87/2007 vom 18. Juni 2007 E. 4.2.3; LORZ/SAUER, a.a.O., S. 394 m.H.).
3.2. Die Vorinstanz führt in diesem Zusammenhang aus, dass "bei provisorischer Prüfung davon auszugehen [sei], dass es dem Rekurrenten klarerweise nicht gelingen wird, die erhebliche Wahrscheinlichkeit einer konkreten und ernsthaften Gefahr i.S.v. Art. 3 EMRK nachzuweisen. Das menschenrechtliche Rückschiebeverbot steht dem Wegweisungsvollzug damit aufgrund einer provisorischen Beurteilung nicht entgegen."
Der Beschwerdeführer rügt diesbezüglich u.a. eine Verletzung von Art. 3 i.V.m. mit Art. 13 EMRK.
3.3. Nach Art. 13 EMRK hat jede Person, die in ihren in dieser Konvention anerkannten Rechten oder Freiheiten verletzt worden ist, das Recht, bei einer innerstaatlichen Instanz eine wirksame Beschwerde zu erheben, auch wenn die Verletzung von Personen begangen worden ist, die in amtlicher Eigenschaft gehandelt haben. Das Recht auf wirksame Beschwerde ist ein akzessorisches Recht. Eine Verletzung von Art. 13 EMRK kann nur in Verbindung mit einer materiellen Garantie der EMRK (oder eines Zusatzprotokolls) gerügt werden, was im vorliegenden Fall (Art. 3 EMRK) zutrifft. Mit Art. 13 EMRK sollen die Konventionsrechte der Sache nach innerstaatlich garantiert werden (vgl. MARTEN BREUER, in: Karpenstein/Mayer, a.a.O., Art. 13 N. 25). Im Vordergrund steht in der vorliegenden Streitsache die Frage, was eine "wirksame Beschwerde" bedeutet.
Nach der Rechtsprechung muss die Beschwerde sowohl rechtlich als auch tatsächlich wirksam sein (vgl. Urteil des EGMR de Souza Ribeiro gegen Frankreich vom 18. Dezember 2012, Nr. 22689/07, § 78; GRABENWARTER/PABEL, a.a.O., § 24 N. 197; BREUER, in: Karpenstein/ Mayer, a.a.O., Art. 13 N. 42), indem sie die vermeintliche Verletzung beziehungsweise ihr Andauern verhindert (vgl. Urteil des EGMR Kommunistische Partei Russlands gegen Russland vom 19. Juni 2012, Nr. 29400/05, § 82). Hinsichtlich der erforderlichen Prüfungsintensität von Art. 13 EMRK (vgl. BREUER, in: Karpenstein/Mayer, a.a.O., Art. 13 N. 47) ist das betroffene Grundrecht in der Sache zu prüfen. Insofern ist eine blosse Willkürprüfung oder Überprüfung der Massnahme nur auf ihre Gesetzwidrigkeit nicht mit Art. 13 EMRK vereinbar (vgl. Urteil des EGMR Hatton gegen Grossbritannien vom 8. Juli 2003, Nr. 36022/97, § 141; BREUER, in: Karpenstein/Mayer, a.a.O., Art. 13 N. 47; GRABENWARTER/PABEL, a.a.O., § 24 N. 198). Im Hinblick auf eine drohende Verletzung von Art. 3 EMRK ergibt sich aus Art. 13 EMRK das konkrete Erfordernis einer unabhängigen, sorgfältigen und hinreichend schnellen Prüfung der Behauptung, was vor allem aus der Irreversibilität von Verletzungen folgt, die dem Betroffenen durch Handlungen nach Art. 3 EMRK drohen (vgl. Urteil des EGMR de Souza Ribeiro gegen Frankreich vom 18. Dezember 2012, Nr. 22689/07, § 82; Singh gegen Belgien vom 2. Oktober 2012, Nr. 33210/11, § 103; GRABENWARTER/PABEL, a.a.O., § 24 N. 201; MEYER-LADEWIG, a.a.O., Art. 13 N. 15, 18). Dabei muss die Prüfung jeden Zweifel beseitigen ("Un tel examen doit permettre d'écarter tout doute" Singh gegen Belgien vom 2. Oktober 2012, Nr. 33210/11, § 103 i.f., siehe auch § 104).
3.4. Die Vorinstanz hat die Vorbringen des Beschwerdeführers und das tatsächliche Risiko einer Misshandlung lediglich provisorisch geprüft. Sie hat damit im Sinne der Rechtsprechung des EGMR weder die Sachlage noch die Rechtsfrage sorgfältig geprüft. Aufgrund einer provisorischen Prüfung ist es der Vorinstanz offensichtlich auch nicht möglich, jegliche Zweifel über die Verletzung von Art. 3 EMRK zu beseitigen. Die Vorinstanz hat damit das Recht des Beschwerdeführers auf eine wirksame Beschwerde nach Art. 13 i.V.m. Art. 3 EMRK vereitelt. Insofern ist die Interessenabwägung zur Frage der Wiederherstellung der aufschiebenden Wirkung nicht korrekt erfolgt. Die Beschwerde ist deshalb gutzuheissen.
3.5. Zu berücksichtigen ist zusätzlich, dass - wie der Beschwerdeführer auch geltend macht - nach der ständigen Rechtsprechung des EGMR im (in vertretbarer Weise) behaupteten Anwendungsbereich von Art. 2 und 3 EMRK, aber nicht in demjenigen von Art. 8 EMRK, der wirksamen Beschwerde im Sinne von Art. 13 EMRK aufschiebende Wirkung zukommen muss (vgl. Urteil des EGMR Hirsi Jamaa gegen Italien vom 23. Februar 2012, Nr. 27765/09, § 200; de Souza Ribeiro gegen Frankreich vom 18. Dezember 2012, Nr. 22689/07, § 82; Baysakov gegen Ukraine vom 18. Februar 2010, Nr. 54131/08, § 71 ff.; GRABENWARTER/PABEL, a.a.O., § 24 N. 201 mit Hinweisen; MEYER-LADEWIG, a.a.O., Art. 13 N. 15; BREUER, in: Karpenstein/Mayer, a.a.O., Art. 13 N. 51 mit Hinweisen). Angesichts dieses Umstandes kann der gesetzliche Entzug der aufschiebenden Wirkung nach Art. 64 Abs. 3 AuG keine Anwendung finden.
3.6. Schliesslich ist noch darauf hinzuweisen, dass der massgebliche Zeitpunkt für die Anwendung des Art. 3 EMRK der Moment der Ausweisung ist (vgl. Urteil des EGMR Chahal gegen Grossbritannien vom 15. November 1996, Nr. 22414/93, § 86). Im Rahmen des Verfahrens vor Bundesgericht hat das SEM darauf hingewiesen, dass sich nach dem vorinstanzlichen Urteil die Situation aufgrund der breiten Berichterstattung tatsächlich geändert habe und deshalb nun eine Identifizierung des Beschwerdeführers für die irakischen Behörden möglich sei. Dem wird im weiteren Verfahren Rechnung zu tragen sein.
4.
Nach dem Gesagten ist die Beschwerde gutzuheissen, der Entscheid des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht vom 12. August 2016 aufzuheben und dem Rekurs an das Justiz- und Sicherheitsdepartement die aufschiebende Wirkung zu erteilen.
Dem Verfahrensausgang entsprechend werden keine Kosten erhoben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Basel hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, der Entscheid des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht vom 12. August 2016 wird aufgehoben, und dem Rekurs an das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt wird die aufschiebende Wirkung erteilt.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Zur Regelung der Kosten- und Entschädigungsfolgen des kantonalen Verfahrens wird die Sache an die Vorinstanz zurückgewiesen.
5.
Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 14. November 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Errass