Sachverhalt:
A.
A._ ist Staatsangehöriger der Dominikanischen Republik. Am 15. Oktober 1999 kam B._, der gemeinsame Sohn von A._ und der Schweizer Bürgerin C._, auf die Welt. A._ reiste am 16. März 2000 in die Schweiz ein und heiratete C._ am 4. April 2000, worauf ihm eine Aufenthaltsbewilligung erteilt wurde. Vom 15. Dezember 2003 bis 11. März 2004 und vom 31. Mai 2004 bis 4. Januar 2005 hielt er sich in der Dominikanischen Republik bei einer anderen Frau auf, mit welcher er ebenfalls im Jahr 2000 ein Kind gezeugt hatte. Am 23. März 2005 wurde ihm die Niederlassungsbewilligung erteilt. Vom 18. November 2005 bis 24. Mai 2006 weilte er in der Dominikanischen Republik bei seiner anderen Familie. Am 5. April 2006 wurde er erleichtert eingebürgert. Am 1. März 2007 reiste er in die Dominikanische Republik aus. Am 10. Dezember 2007 wurde die Ehe A._ / C._, geb. C._, geschieden. Im Jahr 2008 wurde A._ in der Dominikanischen Republik wieder Vater. Im August 2009 kehrte er in die Schweiz zurück. Am 30. März 2011 erklärte das Bundesamt für Migration die Einbürgerung von A._ für nichtig. Mit Verfügung vom 19. Dezember 2014 wies das Migrationsamt des Kantons Schaffhausen A._ wegen Erlöschens seines Aufenthaltstitels aus der Schweiz weg und lehnte eine Neurteilung einer Aufenthaltsbewilligung ab.
B.
Der Regierungsrat des Kantons Schaffhausen wies den von A._ gegen die Verfügung vom 19. Dezember 2014 erhobenen Rekurs mit Beschluss vom 8. September 2015 ab. Mit Entscheid vom 19. April 2016 wies das Obergericht des Kantons Schaffhausen die von A._ gegen den Regierungsratsbeschluss erhobene Verwaltungsgerichtsbeschwerde ab.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 19. Mai 2016 an das Bundesgericht beantragt A._, der Entscheid des kantonalen Obergerichts sei kostenfällig aufzuheben und das kantonale Migrationsamt sei anzuweisen, ihm eine Aufenthaltsbewilligung zum Familiennachzug zu erteilen. In verfahrensrechtlicher Hinsicht beantragt er, ihm sei im Sinne einer vorsorglichen Massnahme der prozedurale Aufenthalt während hängigem Rechtsmittelverfahren zu gestatten und die unentgeltliche Rechtspflege sowie Verbeiständung zu gewähren.
Die Vorinstanz hat auf die Einreichung einer Vernehmlassung verzichtet. Der kantonale Regierungsrat schliesst auf kostenfällige Abweisung der Beschwerde. Mit Verfügung vom 20. Mai 2016 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts dem Beschwerdeführer das Recht auf prozeduralen Aufenthalt erteilt.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wurde unter Einhaltung der gesetzlichen Frist (<ref-law>) und Form (<ref-law>) eingereicht und richtet sich gegen einen Endentscheid einer letzten oberen kantonalen Instanz (<ref-law>; <ref-law>) in einer Angelegenheit des öffentlichen Rechts (<ref-law>).
1.2. Nach <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen ausgeschlossen, auf deren Erteilung weder das Bundes- noch das Völkerrecht einen Rechtsanspruch einräumen. Einzutreten ist auf Beschwerden, die sich gegen eine Nichtverlängerung einer Aufenthaltsbewilligung richten, sofern in vertretbarer Weise ein Anspruch auf eine Verlängerung geltend gemacht wird; ob der Anspruch besteht, ist Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.1 S. 179 f.; Urteil 2C_575/2013 vom 7. Februar 2014 E. 1.1). Der Beschwerdeführer macht geltend, er habe gestützt auf seinen Anspruch auf Familienleben mit seinem minderjährigen Sohn ein Recht auf Verlängerung seiner Aufenthaltsbewilligung (Art. 8 EMRK). Die Beschwerde ist zulässig und der Beschwerdeführer dazu legitimiert (<ref-law>). Auf die Beschwerde ist in dem Umfang, wie sie sich inhaltlich gegen die Nichterteilung einer Aufenthaltsbewilligung richtet, einzutreten.
1.3. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 und Art. 96 BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (<ref-law>), grundsätzlich nur die geltend gemachten Vorbringen, sofern allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.6 S. 280 mit Hinweis). Die Verletzung von Grundrechten sowie von kantonalem und interkantonalem Recht untersucht es in jedem Fall nur insoweit, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 2.2 S. 232; <ref-ruling> E. 2.2 S. 246).
1.4. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zu Grunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (<ref-law>). Offensichtlich unrichtig festgestellt ist ein Sachverhalt, wenn er willkürliche Feststellungen beinhaltet (<ref-ruling> E. 4.1.2 S. 62). Die dem Bundesgericht durch <ref-law> eingeräumte Befugnis, die Sachverhaltsfeststellung der Vorinstanz zu berichtigen oder zu ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung von <ref-law> beruht, entbindet den Beschwerdeführer nicht von seiner Rüge- und Substanziierungspflicht (<ref-ruling> E. 6.2 S. 288). Die betroffene Person muss rechtsgenügend dartun, dass und inwiefern der festgestellte Sachverhalt in diesem Sinne mangelhaft erscheint und die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 in Verbindung mit Art. 42 Abs. 2 und <ref-law>); rein appellatorische Kritik an der Sachverhaltsermittlung und an der Beweiswürdigung genügt den Begründungs- bzw. Rügeanforderungen nicht (vgl. <ref-ruling> E. 10.1 S. 445 mit Hinweisen). Obwohl nicht ausdrücklich im Gesetz erwähnt, beruht auch eine unvollständige Sachverhaltsfeststellung auf einer Rechtsverletzung. Was rechtserheblich ist, bestimmt das materielle Recht; eine in Verkennung der Rechtserheblichkeit unvollständige Erstellung der für die rechtliche Beurteilung massgeblichen Tatsachen stellt demzufolge eine Verletzung materiellen Rechts dar (<ref-ruling> E. 1.4 S. 68, 134 V 53 E. 4.3 S. 62; ULRICH MEYER, Wege zum Bundesgericht - Übersicht und Stolpersteine, ZBJV 146/2010 S. 857).
2.
Der Beschwerdeführer rügt, die Vorinstanz habe Art. 8 EMRK verletzt und den dafür rechtserheblichen Sachverhalt offensichtlich unrichtig erhoben. Die Verweigerung einer Aufenthaltsbewilligung und seine Wegweisung aus der Schweiz erweise sich angesichts seiner engen Beziehung in affektiver und wirtschaftlicher Hinsicht zu seinem Sohn mit Schweizer Bürgerrecht als ein unverhältnismässiger Eingriff in seinen konventionsrechtlich garantierten Anspruch auf Familienleben, weshalb Art. 8 EMRK verletzt sei. Die Vorinstanz, die ungeachtet dessen, dass die erste Rechtsmittelinstanz ausdrücklich nicht bestritten habe, dass er ein enges Verhältnis zu seinem Sohn unterhalte, trotz fehlender anderslautender Tatsachen ein solches enges Verhältnis verneint habe, habe den für die Anwendung von Art. 8 EMRK erheblichen Sachverhalt willkürlich und damit qualifiziert falsch erhoben.
2.1. Anfechtungsobjekt des erstinstanzlichen Rechtsmittelverfahrens vor dem kantonalen Regierungsrat war nicht die Verfügung vom 30. März 2011, mit welcher das Staatssekretariat für Migration die Einbürgerung des Beschwerdeführers für nichtig erklärt hatte, sondern die Verfügung vom 19. Dezember 2014 des kantonalen Migrationsamts betreffend Wegweisung und Ablehnung Neurteilung einer Aufenthaltsbewilligung. Streitgegenstand des bundesgerichtlichen Verfahrens - der sich im Laufe des Verfahrens grundsätzlich nur verengen, aber nicht erweitern kann (<ref-ruling> E. 5 S. 174; Urteile 2C_961/2013 vom 29. April 2014 E. 3.3; 2C_930/2012 vom 10. Januar 2013 E. 1.1) - ist somit nicht die Nichtigerklärung des Schweizer Bürgerrechts, sondern die Erteilung eines neuen Aufenthaltstitels. Aufgrund welcher Rechtsgrundlagen sich ein allfälliger Bewilligungsanspruch ergibt, ist nicht Frage des Streitgegenstandes, sondern der Begründung (Urteile 2C_1140/2015 vom 7. Juni 2016 E. 2.2.1; 2C_961/2013 vom 29. April 2014 E. 3.4). Mit der Nichtigerklärung des Schweizer Bürgerrechts wird die ausländische Person in den Zustand zurückversetzt, in welchen sie sich vor der Einbürgerung befand (<ref-ruling> E. 3.4 S. 7). Grundsätzlich würde die parallele Beziehung, die der Beschwerdeführer neben seiner Ehe mit einer Schweizer Bürgerin mit einer weiteren Frau in der Dominikanischen Republik geführt und den Behörden verschwiegen hat, auch den Widerruf einer (wiederauflebenden) Niederlassungsbewilligung (Art. 63 AuG) oder einer Aufenthaltsbewilligung (Art. 62 AuG) rechtfertigen (<ref-ruling> E. 3.2 S. 267). Vorliegend stützte der Beschwerdeführer seinen Bewilligungsanspruch im vorinstanzlichen Verfahren jedoch nicht (mehr) auf seine mittlerweile geschiedene Ehe mit einer schweizerischen Staatsbürgerin, sondern auf seine Beziehung zu seinem in der Schweiz lebenden minderjährigen Sohn mit Schweizer Bürgerrecht. Dabei handelt es sich um einen im vorinstanzlichen Verfahren zulässigerweise vorgebrachten neuen sachverhaltlichen Umstand (vgl. Urteil 2C_1140/2015 vom 7. Juni 2016 E. 2.2.1), gestützt auf welchen die Vorinstanz die Erteilung eines neuen Aufenthaltstitels geprüft und verworfen hat. In den unten stehenden Erwägungen ist rügegemäss zu prüfen, ob die Vorinstanz das anwendbare Recht zutreffend angewandt und den im Lichte der einschlägigen rechtlichen Bestimmungen erheblichen Sachverhalt offensichtlich unrichtig erhoben hat.
2.2. Art. 8 EMRK verschafft praxisgemäss keinen Anspruch auf Einreise und Aufenthalt in einem bestimmten Staat oder auf Wahl des für das Familienleben am geeignetsten erscheinenden Orts (<ref-ruling> E. 3.2.1 S. 250; <ref-ruling> E. 2b/cc S. 383). Die konventionsrechtliche Garantie auf Privat- und Familienleben ist jedoch berührt, wenn eine staatliche Entfernungs- oder Fernhaltemassnahme eine nahe, echte und tatsächlich gelebte familiäre Beziehung einer in der Schweiz gefestigt anwesenheitsberechtigten Person beeinträchtigt, ohne dass es dieser zum Vornherein möglich bzw. zumutbar wäre, ihr Familienleben andernorts zu pflegen (<ref-ruling> E. 3.2 S. 147; <ref-ruling> E. 2.2 S. 319; <ref-ruling> E. 4.1.2 S. 249 f.). Ist der Schutzbereich von Art. 8 EMRK eröffnet, ist zu prüfen, ob die konventionsrechtliche Garantie gestützt auf eine genügende gesetzliche Grundlage und überwiegende öffentliche Interessen zulässigerweise eingeschränkt werden kann (Art. 8 Ziff. 2 EMRK). Welche Interessen in Anwendung von Art. 8 Ziff. 2 EMRK gegeneinander abzuwägen sind, ist jeweils im Einzelfall zu beurteilen. Dem Kindesinteresse kommt bei der Interessenabwägung regelmässig eine gewichtige Bedeutung zu. Das private Interesse eines ausländischen Elternteils am Verbleib im Land vermag das öffentliche Interesse an einer einschränkenden nationalen Einwanderungspolitik regelmässig zu überwiegen, wenn zwischen dem ausländischen Elternteil und seinem im Inland lebenden Kind eine besonders enge Beziehung in affektiver und wirtschaftlicher Hinsicht besteht und sich dieser Elternteil in der Schweiz tadellos verhalten hat (<ref-ruling> E. 3.2 S. 147; <ref-ruling> E. 2.2 S. 319; vgl. bereits <ref-ruling> E. 3c S. 5 f.). Das Kindesinteresse, wenn möglich mit beiden Elternteilen in der Schweiz aufwachsen zu können, überwiegt demnach in einer Gesamtbetrachtung, wenn im Wesentlichen ausschliesslich Gründe der Zuwanderungssteuerung den privaten Interessen bereits anwesenheitsberechtigter Personen gegenüber stehen, nicht indessen, wenn es zusätzlich darum geht, die öffentliche Sicherheit und Ordnung vor der Gefahr weiterer (gewichtiger) Straftaten zu schützen (Urteile 2C_387/2014 vom 3. März 2015 E. 4.4.1; 2C_740/2014 vom 27. April 2015 E. 4.2.5). Das Bundesgericht hat das Kriterium des tadellosen Verhaltens bisher streng gehandhabt und diesbezüglich seine Praxis nicht relativiert (vgl. BGE <ref-ruling> E. 2.5 S. 321). Es hat diese jüngst einzig bei einer ausländischen Person etwas abgeschwächt, die nicht mehr im gemeinsamen Haushalt mit dem schweizerischen Ehegatten lebte, jedoch über das Kind mit schweizerischer Nationalität - ohne es in der Obhut zu haben - wegen der fortbestehenden (formellen) Ehebeziehung noch die elterliche Sorge ausübte und zudem die Beziehung zum Kind tatsächlich sehr eng war (Treffen mehrere Male pro Woche; <ref-ruling> E. 4.3 und 4.4 S. 149 ff.). Die Praxis, in Bezug auf das Kriterium des tadellosen Verhaltens gewisse "untergeordnete" Vorkommnisse abweichend von BGE <ref-ruling> in einer Gesamtbetrachtung etwas weniger stark zu gewichten, kommt nur in spezifischen Fällen bzw. bei besonderen Umständen infrage; diese müssen es ausnahmsweise rechtfertigen, allfällige (untergeordnete) Verstösse gegen die öffentliche Ordnung (bspw. untergeordnete ausländer- oder ordnungsrechtliche Delinquenz; kurzer, unverschuldeter Sozialhilfebezug) nicht notwendigerweise so stark zu gewichten, dass sie zum Vornherein die anderen Kriterien (Grad der tatsächlichen affektiven und wirtschaftlichen Intensität der Beziehung zum Kind, zivilrechtliche Regelung der familiären Verhältnisse, Dauer der Beziehung und des Aufenthalts, Grad der Integration aller Beteiligten, Kindesinteresse usw.) aufzuwiegen vermögen (Urteile 2C_728/2014 vom 3. Juni 2015 E. 4.1; 2C_723/2014 vom 6. August 2015 E. 2.3).
2.3. Der Beschwerdeführer kann sich mit Hinblick auf seinen im Zeitpunkt des angefochtenen Urteils knapp noch minderjährigen Sohn mit gefestigtem Aufenthaltsrecht in der Schweiz auf Art. 8 EMRK berufen. Der Jugendliche ist in der Schweiz geboren und aufgewachsen, weshalb dem Beschwerdeführer und ihm ein Familienleben in der Dominikanischen Republik nicht ohne Weiteres zumutbar ist. Die Vorinstanz hat erwogen, dass der Beschwerdeführer nicht nur ein gerichtsübliches Besuchsrecht ausübt, sondern (ungeachtet der mittlerweile erfolgten Scheidung von der Kindsmutter) mit seinem Sohn im selben Haushalt lebt, sich die Betreuung mit der geschiedenen Ehefrau teilt und die Kinderalimente regelmässig bezahlt, weshalb grundsätzlich von einer in wirtschaftlicher und affektiver Hinsicht besonders engen Beziehung zu diesem Jugendlichen auszugehen sei (angefochtenes Urteil, E. 2.4.3, S. 11). Die Rüge, die Vorinstanz habe den im Lichte von Art. 8 EMRK erheblichen Sachverhalt, die der Würdigung der Beziehungsnähe in tatsächlicher Hinsicht zu Grunde liegen, offensichtlich unrichtig festgestellt, erweist sich als unbegründet. Als ebenso unbegründet erweist sich auch die Rüge, die Vorinstanz habe die auf dem Spiel stehenden Interessen unzutreffend gegeneinander abgewogen. Zwar vermag in einer Gesamtbetrachtung das Interesse eines Kindes, seine bisherige enge affektive und wirtschaftliche Beziehung zu einem ausländischen Elternteil weiterhin aufrechtzuerhalten, ein ausschliesslich durch Zuwanderungssteuerung begründetes öffentliches Interesse regelmässig aufzuwiegen, wenn der ausländische Elternteil sich tadellos verhalten hat (vgl. oben, E. 2.2). Das Verhalten des Beschwerdeführers, der während seinem zwar langjährigen Aufenthalt in der Schweiz mehrmals (15. Dezember 2003 bis 11. März 2004, 31. Mai 2004 bis 4. Januar 2005, 18. November 2005 bis 24. Mai 2006, 1. März 2007 bis August 2009) zwecks Pflege einer eigentlichen Parallelfamilie in seinen Heimatstaat zurückkehrte und diese Parallelfamilie den Behörden verschwieg, kann nicht mehr als ein untergeordneter Verstoss gegen die öffentliche Ordnung bezeichnet werden, der in einer Gesamtbetrachtung als nicht besonders schwerwiegend einzustufen ist. Dies gilt auch für die Fr. 4'000.--, die er unbestrittenermassen anlässlich seiner Ausreise am 1. März 2007 seiner geschiedenen Ehefrau entwendet und erst auf ihren Druck hin wieder zurückbezahlt hat. Angesichts dessen, dass der in der Schweiz lebende Sohn das Mündigkeitsalter fast erreicht und die Erziehungsaufgabe des Beschwerdeführers für dieses Kind praktisch beendet ist, vermag das Kindeswohl vorwiegend das öffentliche Interesse an der Ausreise des Beschwerdeführers, der sich seinen Aufenthaltstitel durch falsche Angaben erschlichen hat, nicht aufzuwiegen. Die Beschwerde wegen Verletzung von Art. 8 EMRK erweist sich als unbegründet und ist abzuweisen.
3.
Dem unterliegenden Beschwerdeführer, dessen Bedürftigkeit bereits im vorinstanzlichen Verfahren ausgewiesen war, wird auch für das bundesgerichtliche Beschwerdeverfahren die unentgeltliche Rechtspflege und Verbeiständung durch den unterzeichneten Rechtsvertreter gewährt (<ref-law>). Die Gerichtskosten von Fr. 2'000.-- werden einstweilen auf die Gerichtskasse genommen. Der amtliche Rechtsbeistand wird aus der Gerichtskasse entschädigt. Der Beschwerdeführer hat der Gerichtskasse Ersatz zu leisten, wenn er später dazu in der Lage ist (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden einstweilen auf die Gerichtskasse genommen.
3.
Rechtsanwalt Bernhard Jüsi wird aus der Gerichtskasse eine Entschädigung von Fr. 1'872.50 ausgerichtet.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Obergericht des Kantons Schaffhausen und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 6. April 2017
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Mayhall