Sachverhalt:
A.
X._ (geb. 1967) stammt aus Jordanien. Am 12. Oktober 1998 reiste er in die Schweiz ein und beantragte Asyl. Im Mai 2000 lernte er die 13 Jahre ältere Z._ kennen. Die beiden heirateten im Dezember 2000. In der Folge erhielt X._ eine Aufenthaltsbewilligung und zog sein Gesuch um Asyl zurück.
B.
Im September 2003 stellt X._ ein Gesuch um erleichterte Einbürgerung. Seit dem 1. November 2003 verfügte er über eine Zweitwohnung in der Nähe der ehelichen Wohnung. Dem Gesuch um Einbürgerung wurde am 24. Juni 2004 stattgegeben. Am 8. Oktober 2004 wurden Eheschutzmassnahmen angeordnet und das Getrenntleben gerichtlich festgestellt. Im Februar 2005 reichten die Ehegatten ein gemeinsames Scheidungsbegehren ein; am 6. Juni 2005 wurde die Ehe geschieden. Das Bundesamt für Migration teilte X._ in der Folge mit, es erwäge die Nichtigerklärung der erleichterten Einbürgerung.
C.
Am 16. Dezember 2005 heiratete X._ die Jordanierin Y._. Z._ war mittlerweile - die Vorinstanz hat nicht festgestellt, an welchem Datum - verstorben. Am 19. April 2006 reichte X._ ein erstes, am 28. Mai 2010 ein weiteres Gesuch um Familiennachzug für seine jordanische Ehegattin ein. Dem zweiten Gesuch wurde am 29. Juli 2010 stattgegeben. Am 6. August 2010 reiste Y._ in die Schweiz ein und erhielt eine Aufenthaltsbewilligung. Am 6. Juli 2011 wurden dem Ehepaar in St. Gallen die beiden Kinder A._ und B._ geboren.
D.
Mit Verfügung vom 1. Mai 2009 erklärte das Bundesamt für Migration die im Jahr 2004 erfolgte erleichterte Einbürgerung für nichtig. Das Bundesgericht wies eine hiergegen erhobene Beschwerde letztinstanzlich ab (Urteil 1C_476/2010 vom 13. Dezember 2010).
Bereits zuvor, am 17. Oktober 2010, stellte X._ ein Gesuch um Wiedererteilung einer Aufenthaltsbewilligung. Am 5. Januar 2011 ersuchte er um Erteilung einer Niederlassungsbewilligung. Das Migrationsamt wies die Gesuche um Erteilung einer Aufenthalts- bzw. einer Niederlassungsbewilligung mit Verfügung vom 21. März 2011 ab. X._ und seine Gattin erhoben hiergegen Rekurs beim Sicherheits- und Justizdepartement des Kantons St. Gallen, welches diesen am 9. März 2012 abwies. Eine hiergegen gerichtete Beschwerde an das Verwaltungsgericht des Kantons St. Gallen blieb ohne Erfolg (Urteil vom 15. Oktober 2012).
E.
Mit Eingabe vom 11. November 2012 erheben X._ (Beschwerdeführer) und seine Gattin Y._ (Beschwerdeführerin) Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragen dem Bundesgericht, das Urteil des Verwaltungsgerichts sei aufzuheben. Dem Beschwerdeführer sei eine Niederlassungsbewilligung, eventuell eine Aufenthaltsbewilligung zu erteilen und vom Widerruf der Aufenthaltsbewilligung der Beschwerdeführerin sei abzusehen; ihr und den Kindern sei der weitere Aufenthalt in der Schweiz zu gestatten. Die Beschwerdeführenden beantragen zudem die unentgeltliche Prozessführung und Verbeiständung.
Mit Verfügung vom 16. November 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.
Das Sicherheits- und Justizdepartement und das Verwaltungsgericht des Kantons St. Gallen wie auch das Bundesamt für Migration beantragen, die Beschwerde sei abzuweisen.

Erwägungen:
1.
1.1. Die Nichtigerklärung des Schweizerbürgerrechts des Beschwerdeführers in Anwendung von Art. 41 des Bundesgesetzes vom 29. September 1952 über Erwerb und Verlust des Schweizer Bürgerrechts (Bürgerrechtsgesetz, BüG; SR 141.0) ist rechtskräftig und steht hier nicht mehr infrage. Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss <ref-law> unzulässig gegen Entscheide betreffend die Erteilung oder Verweigerung von Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Der Beschwerdeführer war von 2000 bis 2005 mit einer Schweizerin verheiratet; er macht in vertretbarer Weise einen potenziellen Anspruch auf eine Niederlassungsbewilligung nach Art. 42 Abs. 3 AuG bzw. eventualiter auf eine Aufenthaltsbewilligung nach Art. 50 Abs. 1 lit. a und b AuG geltend. Auf die Beschwerde ist demnach einzutreten. Ob die jeweiligen Voraussetzungen tatsächlich gegeben sind, bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.1 S. 179 f.).
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>; vgl. <ref-ruling> E. 1.5 S. 146 f.). Die Eingabe vom 20. März 2013 (Geburt eines weiteren Kindes; Hinweise auf die Flüchtlingssituation in Jordanien) bleibt unbeachtlich.
1.3. Soweit mit dem Rechtsmittel die Aufhebung der Entscheide der unteren kantonalen Instanzen verlangt wird, kann darauf nicht eingetreten werden. Das Anfechtungsobjekt ist ausschliesslich das Urteil des Verwaltungsgerichts des Kantons St. Gallen vom 15. Oktober 2012 (Devolutiveffekt; vgl. <ref-law>; <ref-ruling> E. 1.4 S. 144; <ref-ruling> E. 1 S. 441, mit Hinweisen).
2.
Der Beschwerdeführer macht geltend, sein Anspruch auf rechtliches Gehör (<ref-law>) sei verletzt, weil die Vorinstanz "allzu unkritisch" auf einzelne Äusserungen der mittlerweile verstorbenen ersten Ehegattin des Beschwerdeführers abgestellt habe. Dagegen habe sie den angebotenen Beweis der Befragung ihrer Kinder abgelehnt.
2.1. Der Anspruch auf rechtliches Gehör beinhaltet das Recht des Betroffenen, sich vor Erlass eines in seine Rechtsstellung eingreifenden Entscheides zur Sache zu äussern, sowie das Recht auf Abnahme der rechtzeitig und formrichtig angebotenen, rechtserheblichen Beweismittel (<ref-ruling> E. 5.1 S. 293; <ref-ruling> E. 3.2 S. 494; <ref-ruling> E. 2b S. 56). Das Gericht kann auf die Abnahme von Beweisen verzichten, wenn es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür annehmen kann, seine Überzeugung werde durch weitere Beweiserhebungen nicht geändert (<ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 3 S. 157).
2.2. Die Vorinstanz hatte genügend relevante Informationen zur Verfügung, um sich - auch ohne zusätzliche Anhörung der vorgeschlagenen Zeugen - ein Bild über die eheliche Gemeinschaft des Beschwerdeführers und seiner ersten Gattin zu machen. Sowohl der Beschwerdeführer als auch seine Schweizer Gattin hatten sich mehrmals zu den Umständen der Ehe geäussert; die Vorinstanz hat sich mit diesen Unterlagen auseinandergesetzt. Das Verwaltungsgericht hat die Äusserungen der Gattin im Gegensatz zum Beschwerdeführer nicht als widersprüchlich betrachtet. Sie hat in nachvollziehbarer Weise dargelegt, weshalb sie deren Äusserungen Überzeugungskraft zumass. Entgegen der Auffassung des Beschwerdeführers hat sich die Vorinstanz auch nicht auf diese Aussagen, sondern auf das primäre und objektivierbare Kriterium der nach aussen wahrnehmbaren Wohngemeinschaft gestützt (vgl. <ref-ruling> E. 2 S. 231; <ref-ruling> E. 3.1.2 S. 347; Urteil 2C_903/2011 vom 11. Juni 2012 E. 3.2; unten E. 3.4 und 4). Eine Verletzung von <ref-law> liegt nicht vor (vgl. <ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 2.1 S. 428 f.).
3.
3.1. Mit der - rechtskräftigen - Nichtigerklärung der Einbürgerung wurde der Beschwerdeführer ausländerrechtlich in die gleiche Rechtsstellung wie vor der Einbürgerung versetzt (vgl. <ref-ruling> E. 3.2 S. 5 f.; Urteil 2C_431/2010 vom 25. Juli 2011 E. 1.1). War die betroffene Person vor der Einbürgerung im Besitz einer Niederlassungsbewilligung, besteht diese zwar fort, unterliegt ihrerseits jedoch wieder den ausländerrechtlichen Erlöschens- oder Widerrufsgründen (vgl. Art. 51 bzw. Art. 63 AuG; Urteil 2C_226/2011 vom 14. November 2011 E. 2). War die betroffene Person vor der Einbürgerung im Besitz einer Aufenthaltsbewilligung, lebt diese entgegen der Ansicht des Beschwerdeführers nicht automatisch wieder auf. Vielmehr ist aufgrund der aktuellen Sachlage neu über ein allfälliges Anwesenheitsrecht zu entscheiden (vgl. <ref-ruling> E. 3.2 S. 5 f.; Urteil 2C_431/2010 vom 25. Juli 2011 E. 1.1), dabei gelten die allgemeinen Zulassungsvoraussetzungen des AuG (vgl. <ref-law> [SR 142.201]).
3.2. Unter Vorbehalt von Art. 51 Abs. 1 AuG haben ausländische Ehegatten von Schweizer Bürgern nach 5 Jahren ununterbrochenen und ordnungsgemässen Aufenthalts Anspruch auf Erteilung der Niederlassungsbewilligung (Art. 42 Abs. 3 AuG). Da die Ehe des Beschwerdeführers mit seiner ersten Gattin weniger als fünf Jahre dauerte, bis sie im Juni 2005 geschieden wurde, fällt ein Anspruch auf Erteilung der Niederlassungsbewilligung nach Art. 42 Abs. 3 AuG zum Vornherein ausser Betracht (Urteile 2C_413/2013 vom 28. Juni 2013 E. 2.1; 2C_899/2011 vom 20. April 2012 E. 2.1; 2C_568/2011 vom 16. November 2011 E. 3.2, je mit Hinweisen).
3.3. Unter Vorbehalt von Art. 51 Abs. 1 AuG haben ausländische Ehegatten von Schweizer Bürgern Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit ihrem Partner zusammenwohnen (Art. 42 Abs. 1 AuG). Der Bewilligungsanspruch besteht trotz Auflösens bzw. definitiven Scheiterns der Ehegemeinschaft fort, wenn diese mindestens drei Jahre gedauert und die betroffene ausländische Person sich hier erfolgreich integriert hat (Art. 50 Abs. 1 lit. a AuG; <ref-ruling> E. 3.3.3; Urteile 2C_40/2012 E. 6; 2C_821/2011 vom 22. Juni 2012 E. 2; 2C_886/2011 vom 28. Februar 2012 E. 4.1).
Der Beschwerdeführer hat nach erfolgter Scheidung zwar keinen Anspruch mehr auf Verlängerung seiner Aufenthaltsbewilligung nach Art. 42 Abs. 1 AuG. Sollte er jedoch vor der Scheidung einen Anspruch auf die Aufenthaltsbewilligung nach Art. 42 Abs. 1 in Verbindung mit Art. 50 Abs. 1 lit. a oder b erworben haben, kann er sich nach der Rechtsprechung hierauf auch nach der Beendigung der Ehe berufen (<ref-ruling> E. 1.1.4 S. 149; Urteil 2C_431/2010 vom 25. Juli 2011 E. 1.2), zumal die Vorinstanz explizit nicht vom Vorliegen einer Scheinehe, und damit nicht vom Erlöschen der Ansprüche des Beschwerdeführers nach Art. 51 Abs. 1 AuG ausgegangen ist (vgl. Urteil 2C_682/2012 vom 7. Februar 2013 E. 6.2.2 e contrario; vgl. auch Urteil des BVGer C-130/2012 vom 12. September 2012 E. 7).
3.4. Eine im Sinne von Art. 50 Abs. 1 lit. a AuG relevante Ehegemeinschaft liegt vor, solange dieeheliche Beziehung tatsächlich gelebt wird und ein gegenseitiger Ehewille besteht. Mit Blick auf Art. 49 AuG, der den Ehegatten bei weiterdauernder Familiengemeinschaft gestattet, aus "wichtigen Gründen" getrennt zu leben, was auch bei vorübergehenden Schwierigkeiten in der Ehe kurzfristig der Fall sein kann (vgl. <ref-law>; dazu Urteile 2C_891/2012 vom 7. Juni 2013 E. 2.3; 2C_635/2009 vom 26. März 2010 E. 4.4 mit Hinweisen auf die Entstehungsgeschichte), ist jeweils aufgrund sämtlicher Umstände im Einzelfall zu bestimmen, ab welchem Zeitpunkt die eheliche Gemeinschaft als definitiv aufgelöst zu gelten hat (vgl. <ref-ruling> E. 2 S. 231). Dabei ist auf objektivierbare Kriterien - im Wesentlichen auf die Dauer der nach aussen wahrnehmbaren ehelichen Wohngemeinschaft - abzustellen (BGE <ref-ruling> E. 3.1.2 f. S. 347; Urteile 2C_891/2012 vom 7. Juni 2013 E. 2.1; 2C_903/2011 vom 11. Juni 2012 E. 2.2; 2C_544/2010 vom 23. Dezember 2010 E. 2.2). Die Grenze von drei Jahren gilt dabei absolut (BGE <ref-ruling> E. 3.1.3 S. 347; Urteil 2C_430/2011 vom 11. Oktober 2011 E. 4.1). Selbst wenn die Frist von drei Jahren nur um wenige Wochen oder Tage verpasst wird, besteht kein Anspruch mehr darauf, dass die Bewilligung gestützt auf Art. 50 Abs. 1 lit. a AuG verlängert wird (BGE <ref-ruling> E. 3.1.3 und 3.2.1 S. 347 f.; Urteile 2C_903/2011 vom 11. Juni 2012 E. 2.3; 2C_366/2012 vom 1. Mai 2012 E. 2.1).
4.
4.1. Der Beschwerdeführer reiste im Mai 2000 in die Schweiz ein und heiratete seine Schweizer Gattin am 1. Dezember 2000. Die Eheleute lebten ab dem 7. August 2004 getrennt; die Ehe wurde am 6. Juni 2005 geschieden. Gemäss den Feststellungen der Vorinstanz hatte dem Beschwerdeführer ab dem 1. November 2003, d.h. 2 Jahre und 11 Monate nach der Hochzeit, eine Zweitwohnung zur alleinigen Benutzung zur Verfügung gestanden. Die Vorinstanz wertete diesen Umstand als Indiz dafür, dass das Erfordernis des Zusammenlebens gemäss Art. 42 AuG nicht mehr erfüllt war, und prüfte, ob durch die Rechtsprechung anerkannte wichtige Gründe für ein vorübergehendes Getrenntleben im Sinne von Art. 49 AuG vorlagen, was sie schliesslich - ohne Bundesrecht zu verletzen - verneinte:
4.1.1. Der Beschwerdeführer bringt vor, die Anmietung einer Zweitwohnung habe lediglich "zeitweise" als "Rückszugsort zwecks Deeskalation einer angespannten Lage" gedient. Aufgrund des Wunsches, seiner zu jenem Zeitpunkt bereits erkrankten Schweizer Gattin, oft allein zu sein, habe ein wichtiger Grund im Sinne von Art. 49 AuG bzw. für ein "teilweises living apart together" vorgelegen. Die Ehegemeinschaft habe zu jenem Zeitpunkt jedoch weiter bestanden; dies werde durch die Trennungsvereinbarung von 2004 dokumentiert. Der Beschwerdeführer bringt auch vor, das Bundesgericht sei in seinem Urteil vom 13. Dezember 2010 zur Nichtigerklärung der Einbürgerung von einem bestehenden Ehewillen bis September 2004 ausgegangen.
4.1.2. Im vom Beschwerdeführer herangezogenen Urteil vom 13. Dezember 2010 zur Nichtigerklärung seiner Einbürgerung musste das Bundesgericht die tatsächlichen Verhältnisse nicht unter dem Gesichtswinkel von Art. 42 Abs. 1 bzw. Art. 50 AuG prüfen; in jenem Urteil ist es jedoch gleichermassen von einer seit November 2003 instabilen Gemeinschaft ausgegangen (Urteil 1C_476/2010 vom 13. Dezember 2010 E. 4.3.2 in fine). Die Vorinstanz stellte ihrerseits fest, dass die Ehe seit Beginn von Spannungen geprägt war und für die Anmietung der Zweitwohnung nach weniger als drei Jahren gelebter Ehegemeinschaft keine wichtigen Gründe im Sinne der Rechtsprechung (vgl. oben E. 3.4) vorlagen. Was der Beschwerdeführer hiergegen vorbringt, ist nicht geeignet, die vorinstanzlichen Feststellungen als willkürlich erscheinen zu lassen: Zwar hatte sich das Paar zur Lösung der ehelichen Probleme im August 2003 in eine Therapie begeben. Diese war auf Geheiss des Beschwerdeführers jedoch noch vor dem Bezug der Zweitwohnung bereits wieder abgebrochen worden; es sind zudem keine Hinweise ersichtlich, dass die Zweitwohnung nur vorübergehend angemietet wurde. Die ehelichen Spannungen hielten offenbar vielmehr an und waren - wie dies auch die Schreiben der ersten Gattin des Beschwerdeführers aufzeigen - so gross, dass eine vollständige Rückkehr in die eheliche Wohnung nicht mehr möglich war. Die Gatten nahmen den gemeinsamen Haushalt nicht mehr auf und trennten sich im August 2004 endgültig. Rückblickend kann demnach entgegen der Auffassung des Beschwerdeführers nicht von einer vorübergehenden Trennung gesprochen werden, wie dies <ref-law> in Verbindung mit Art. 49 AuG vorschreibt (vgl. auch Urteile 2C_347/2013 vom 1. Mai 2013 E. 3.2.2; 2C_231/2011 vom 21. Juli 2011 E. 4.6). Entgegen der Ansicht des Beschwerdeführers stellt auch ein freiwilliger Entscheid, teilweise "together apart" zu leben, für sich keinen wichtigen Grund im Sinne von Art. 49 AuG dar (Urteile 2C_831/2012 vom 24. März 2013 E. 6.1.1; 2C_40 vom 15. Oktober 2012 E. 4; 2C_388/2009 vom 9. Dezember 2009 E. 4).
4.1.3. Das Verwaltungsgericht durfte demnach gestützt auf die äusseren Umstände davon ausgehen, es habe ab dem Bezug der Zweitwohnung am 1. November 2003 keine eheliche Gemeinschaft im Sinne von Art. 42 Abs. 1 AuG mehr vorgelegen und es sei kein Anspruch auf Erteilung einer Aufenthaltsbewilligung gemäss Art. 50 Abs. 1 lit. a AuG entstanden. Dass die Eheschutzmassnahmen und das Getrenntleben erst im Oktober 2004 gerichtlich festgestellt wurden und die Ehe - formell - noch bis ins Jahr 2005 weiter bestand, ist in diesem Zusammenhang nicht von Bedeutung (vgl. <ref-ruling> E. 3.2 S. 117; Urteile 2C_891/2012 vom 7. Juni 2013 E. 2.1; 2C_647/2010 vom 10. Februar 2011 E. 3.1).
Da die erforderlichen 3 Jahre Ehegemeinschaft im Sinne von Art. 42 Abs. 1 in Verbindung mit Art. 50 Abs. 1 lit. a AuG nicht vorliegen, erübrigt es sich, die Hinweise auf eine erfolgreiche Integration näher zu prüfen.
4.2. Der Beschwerdeführer beruft sich auf einen Härtefall im Sinne von Art. 50 Abs. 1 lit. b und Abs. 2 AuG. Danach besteht der Bewilligungsanspruch nach einer gescheiterten Ehe bzw. Familiengemeinschaft fort, falls wichtige persönliche Gründe einen weiteren Aufenthalt der ausländischen Familienmitglieder in der Schweiz erforderlich machen (vgl. BGE <ref-ruling> E. 3.2 S. 348 ff.). Entscheidend ist, ob die persönliche, berufliche und familiäre Eingliederung der betroffenen ausländischen Person bei einer Rückkehr in ihre Heimat als stark gefährdet zu gelten hätte und nicht, ob ein Leben in der Schweiz einfacher wäre und - aus welchen Gründen auch immer - vorgezogen würde (vgl. BGE <ref-ruling> E. 3.2.3 S. 350). Ein persönlicher, nachehelicher Härtefall setzt aufgrund der gesamten Umstände eine erhebliche Intensität der Konsequenzen für das Privat- und Familienleben voraus, die mit der Lebenssituation nach dem Dahinfallen der abgeleiteten Anwesenheitsberechtigung verbunden sein muss (vgl. BGE <ref-ruling> E. 3.2.3 S. 350; Urteil 2C_65/2012 vom 22. März 2013 E. 6 [zur Publikation vorgesehen]). Nach der Rechtsprechung kann der Tod desjenigen Ehegatten, welcher das Anwesenheitsrecht vermittelt hat, einen nachehelichen Härtefall im Sinn von Art. 50 Abs. 1 lit. b AuG begründen. Ein solcher Härtefall wird vor Ablauf der Dreijahresfrist vermutet, wenn sich keine Zweifel am tatsächlichen Bestehen der Ehe und an der Intensität der Verbundenheit der Ehegatten ergeben (<ref-ruling> E. 3.3 S. 396; <ref-ruling> E. 3.1 S. 3 ff.; Urteil 2C_669/2012 vom 5. Mai 2013 E. 3.3).
4.3.
4.3.1. Vorliegend erfolgten die definitive Aufgabe der Ehegemeinschaft und die Scheidung, bevor die Schweizer Gattin des Beschwerdeführers verstorben ist. Der Beschwerdeführer muss nicht das Leben in der Schweiz aufgeben, das er zusammen mit seiner verstorbenen Partnerin in der Schweiz geführt hat. Der Hinschied seiner ersten Gattin begründet für ihn kein Härtefall im Sinne von Art. 50 Abs. 1 lit. b AuG (<ref-ruling> E. 3.3 S. 396; <ref-ruling> E. 3.2 S. 6; Urteil 2C_669/2012 vom 5. Mai 2013 E. 3.3).
4.3.2. Entgegen der Auffassung des Beschwerdeführers ist auch nicht ersichtlich, inwiefern die Rückkehr nach Jordanien ihn vor besondere Probleme stellen würde, die in einem hinreichend engen Zusammenhang zur anspruchsbegründenden Ehe und dem damit verbundenen bisherigen (bewilligten) Aufenthalt in der Schweiz stünden (vgl. BGE <ref-ruling> E. 3.2.3 S. 350). Der Beschwerdeführer ist erst mit 31 Jahren in die Schweiz eingereist. Er hat die prägenden Jugendjahre und einen Grossteil seines Lebens in seinem Heimatland verbracht. Ebenso verfügt er über verschiedene Verwandte in seinem Herkunftsland; dort leben auch die Verwandten seiner jordanischen Gattin. Aufgrund des verbindlich festgestellten Sachverhalts, dessen Richtigkeit der Beschwerdeführer diesbezüglich nur appellatorisch und damit nicht rechtsgenügend kritisiert (vgl. Art. 105 und <ref-law>; <ref-ruling> E. 1.4.3), bestehen keine Hinweise, wonach seine Wiedereingliederung in der Heimat ernstlich gefährdet erschiene. Dass die Arbeitslosenquote in Jordanien höher liegt als in der Schweiz, vermag daran nichts zu ändern (vgl. nebst BGE <ref-ruling> E. 3.2.3 S. 350 auch die Urteile 2C_489/2011 vom 16. Juni 2011 E. 2.2 sowie 2C_216/2009 vom 20. August 2009 E. 3).
4.3.3. Der Beschwerdeführer legt schliesslich keine über eine normale Integration hinausgehenden privaten Bindungen gesellschaftlicher oder beruflicher Natur dar (vgl. <ref-ruling> E. 3.2.1 S. 286, 126 II 377 E. 2c S. 384 ff.). Auch wenn es ihm nach einer längeren Anwesenheit in der Schweiz zweifelsohne nicht leicht fallen wird, wieder in seine Heimat zurückzukehren, ist in Gesamtwürdigung der Umstände davon auszugehen, dass kein Härtefall im Sinne von Art. 50 Abs. 1 lit. b AuG vorliegt. Die Vorinstanz hat durch ihre Interessenabwägung weder Art. 50 AuG noch Art. 8 EMRK und <ref-law> (Schutz der Privatsphäre) verletzt.
4.4. Steht dem Beschwerdeführer kein Anspruch auf eine Anwesenheits- oder Niederlassungsbewilligung zu, entfällt auch jede Grundlage für entsprechende Ansprüche seiner zweiten Ehefrau und der beiden gemeinsamen Kinder. Auch seine Gattin ist erst im Alter von 32 Jahren in die Schweiz eingereist; ihre Einreise erfolgte im Jahr 2010 und liegt demnach noch nicht lange zurück. Der Beschwerdeführer und die Beschwerdeführerin wurden denn auch - wie sie selbst anfügen - darauf hingewiesen, dass der Familiennachzug für die Gattin vorbehältlich des Entscheids über die Nichtigkeit der Einbürgerung erteilt werde. Da die Beschwerdeführerin und die im Jahr 2011 geborenen Kinder über kein gefestigtes Aufenthaltsrecht verfügen und zusammen mit dem Beschwerdeführer in ihr Heimatland zurückkehren, liegt kein Eingriff in den Schutzbereich des Familienlebens im Sinne von Art. 8 EMRK bzw. <ref-law> vor (vgl. für den Status der Kinder auch MINH SON NGUYEN, Migrations et relations familiales: de la norme à la jurisprudence et vice versa, in: Amarelle/ Christen/Nguyen [Hrsg.], Migrations et regroupement familial, 2012, S. 109 ff., dort S. 253 f.).
5.
5.1. Nicht einzutreten ist auf die Eingabe schliesslich, soweit der Beschwerdeführer eine Verletzung von Art. 30 Abs. 1 lit. b und k AuG geltend macht (<ref-law>). Bei der angerufenen Bestimmung geht es um eine Ermessensbewilligung, welche von den Kantonen im Rahmen von Art. 96 AuG erteilt werden kann. Das Bundesgericht könnte die Anwendung von Art. 30 Abs. 1 lit. b und k AuG durch die kantonalen Behörden nur im Rahmen der subsidiären Verfassungsbeschwerde (<ref-law>) und der dort zulässigen Rüge der Verletzung verfassungsmässiger Rechte (<ref-law>) prüfen. Entsprechende Rügen werden vom Beschwerdeführer im Zusammenhang mit dem kantonalen Ermessensentscheid nicht rechtsgenügend begründet erhoben (vgl. BGE <ref-ruling> E. 3.2.1 S. 348; Urteile 2C_65/2012 vom 22. März 2013 E. 7.1 [zur Publikation vorgesehen]; 2C_803/2010 vom 14. Juni 2011 E. 3), zudem fehlte ihm die Legitimation hierzu, da er gestützt auf Art. 30 Abs. 1 lit. b und k AuG resp. für die Überprüfung eines Ermessensentscheids nur das Willkürverbot anrufen könnte (vgl. <ref-ruling> E. 6 S. 198 ff.).
5.2. Trotz fehlender Legitimation in der Sache selbst ist die ausländische Person jedoch zur Rüge berechtigt, ihr zustehende Verfahrensgarantien, namentlich ihr Anspruch auf rechtliches Gehör, seien verletzt worden. Nicht zu hören sind dabei jedoch wiederum Vorbringen, die im Ergebnis auf die Überprüfung des Sachentscheids abzielen, wie die Behauptung, dass die Begründung des angefochtenen Entscheids unvollständig oder zu wenig differenziert ausgefallen sei, sich nicht mit sämtlichen Argumenten auseinandersetze oder dass die Parteivorbringen willkürlich gewürdigt worden seien; ebenso wenig ist der Vorwurf zu hören, der Sachverhalt sei unvollständig oder sonst wie willkürlich festgestellt oder Beweisanträge seien wegen willkürlicher antizipierter Beweiswürdigung abgelehnt worden (vgl. zur Weiterführung dieser so genannten "Star-Praxis" unter der Herrschaft des Bundesgerichtsgesetzes s. <ref-ruling> E. 3.2 S. 436 f.).
5.3. Der Beschwerdeführer wirft der Vorinstanz vor, sie habe sich nicht näher mit seinen Vorbringen zu Art. 30 Abs. 1 lit. k AuG auseinandergesetzt und macht geltend, die zeitlichen Voraussetzungen für die Erteilung einer Härtefallbewilligung wären erfüllt gewesen. Die Rüge zielt im Ergebnis auf die Überprüfung des Sachentscheids. Soweit er eine Verletzung von Treu und Glauben geltend macht, belegt er nicht, inwiefern die Migrationsbehörde durch ihr Verhalten eine Vertrauensgrundlage geschaffen haben soll (<ref-law>); seine diesbezüglichen Ausführungen gehen materiell zudem nicht über den vom Willkürverbot umfassten Schutzbereich hinaus. Auf die vorliegende Eingabe ist im Zusammenhang mit Art. 30 Abs. 1 lit. b und k AuG demnach mangels eines Rechtsanspruchs bzw. einer zulässigen Gehörsverweigerungsrüge weder als Beschwerde in öffentlich-rechtlichen Angelegenheiten noch als subsidiäre Verfassungsbeschwerde einzutreten.
5.4. Nicht einzutreten ist auf die Beschwerde auch insoweit, als der Beschwerdeführer unabhängig vom Ergebnis des Entscheides über den Aufenthaltsanspruch die Wegweisung anficht. In dieser Hinsicht ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten ebenfalls ausgeschlossen (vgl. <ref-law>). Die Eingabe kann auch nicht als subsidiäre Verfassungsbeschwerde entgegengenommen werden, da der Beschwerdeführer keine genügend substanziierten zulässigen Verfassungsrügen mit Bezug auf die Wegweisung erhebt (vgl. Art. 116 und 117 i.V.m. <ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254, 396 E. 3.1 S. 399; Urteil 2C_236/2011 vom 2. September 2011 E. 1.4).
6.
Die Beschwerde ist als unbegründet abzuweisen, soweit darauf eingetreten werden kann. Da sie sich nicht als aussichtslos erweist und der Beschwerdeführer bedürftig ist, kann die beantragte unentgeltliche Rechtspflege bewilligt und auf die Erhebung von Gerichtskosten verzichtet werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Prozessführung wird gutgeheissen.
2.1. Es werden keine Kosten erhoben.
2.2. Den Beschwerdeführenden wird Rechtsanwalt Dr. Peter Kreis als Rechtsbeistand beigegeben. Diesem wird aus der Gerichtskasse eine Entschädigung von Fr. 2'000.-- ausgerichtet.
3.
Dieses Urteil wird den Verfahrensbeteiligten sowie dem Verwaltungsgericht des Kantons St. Gallen und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 11. Juli 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Hänni