Sachverhalt:
A.
A.a. A._ (geb. 1973), Staatsangehöriger der Republik Kosovo, ersuchte kurz nach seiner Einreise in die Schweiz am 25. Juni 2002 erfolglos um Asyl. Am 2. September 2002 heiratete er die Schweizerin B._ und erhielt vom Kanton Aargau im Rahmen des Familiennachzugs am 4. November 2002 eine Aufenthaltsbewilligung. Am 11. Dezember 2007 wurde letztere in eine Niederlassungsbewilligung umgewandelt, wobei im entsprechenden Gesuch vom 30. November 2007 drei aussereheliche Kinder unter dem Familiennamen von A._, jeweils mit dem Namen der Kindsmutter C._, aufgeführt wurden.
Per 18. April 2008 wurde die Ehe mit B._ geschieden, worauf das Bundesamt für Migration (BFF; heute Staatssekretariat für Migration [SEM]) mit rechtskräftigem Entscheid vom 17. Juli 2008 die kurz zuvor erfolgte erleichterte Einbürgerung wegen falscher Angaben von A._ wieder aufhob. Aus den Akten ergibt sich, dass B._ am 14. August 2008 vom Migrationsamt des Kantons Aargau (heute Amt für Migration und Integration des Kantons Aargau [MIKA]) zur Ehe mit A._ befragt, aufgrund der entsprechenden Aussagen jedoch keine ausländerrechtlichen Massnahmen gegenüber A._ ergriffen wurden.
Am 7. April 2009 stellte A._ ein Familiennachzugsgesuch für drei seiner im Kosovo wohnhaften vier Kinder, nämlich D._ (geb. 27. Juni 1999), E._ (geb. 27. März 2001) und F._ (geb. 25. Juni 2002), auf welches die Sektion Einreise und Arbeit des MIKA nicht eintrat.
A.b. Im August 2011 zogen die vier Kinder von A._ (jüngstes Kind Tochter G._ geb. am 3. Januar 2008, Kindsmutter ist ebenfalls C._), serbische Staatsangehörige, in die Schweiz zu ihrem Vater und wurden von letzterem am 30. August 2011 zur Wohnsitznahme in U._/AG angemeldet. Am 7. Oktober 2011 stellte A._ bei der Gemeinde U._ erneut ein Familiennachzugsgesuch, dieses Mal für seine vier Kinder.
A.c. Die Kindsmutter, C._, heiratete am 8. Mai 2012 den Schweizer H._, reiste am 28. Oktober 2010 in die Schweiz ein und erhielt am 17. Dezember 2012 eine Aufenthaltsbewilligung des Kantons Waadt. Der Kanton Genf bewilligte am 14. Oktober 2013 ihren Kantonswechsel und erteilte ihr eine Aufenthaltsbewilligung, welche am 21. Januar 2016 mit Gültigkeit bis zum 27. Oktober 2017 verlängert wurde.
A.d. Das MIKA teilte A._ am 15. März 2013 mit, dass sein Familiennachzugsgesuch für seine vier Kinder vertieft geprüft werde. Am 20. März 2013 stellte es gegenüber A._ den Widerruf seiner Niederlassungsbewilligung und seine Wegweisung aus der Schweiz in Aussicht und gewährte ihm das rechtliche Gehör. Das Familiennachzugsverfahren wurde gemäss Schreiben des MIKA vom 28. März 2013 bis zum Abschluss des genannten Widerrufsverfahrens sistiert. Am 3. April 2013 heiratete A._ die in der Schweiz niedergelassene österreichische Staatsangehörige I._, wobei diese Ehe am 4. Juli 2016 geschieden wurde.
B.
B.a. Mit Verfügung vom 28. Oktober 2013 widerrief das MIKA die Niederlassungsbewilligung von A._ und erteilte ihm gleichzeitig unter Vorbehalt der Zustimmung des Bundesamtes für Migration (heute Staatssekretariat für Migration) eine Aufenthaltsbewilligung. Mit Einsprache vom 28. November 2013 an den Rechtsdienst des MIKA verlangte A._ die Aufhebung der genannten Verfügung. Im Rahmen des Einspracheverfahrens stellte sich heraus, dass A._ vom 15. November 2013 bis zum 19. Mai 2014 in Serbien in Untersuchungshaft sass, worauf der Rechtsdienst des MIKA A._ mit Schreiben vom 14. Juli 2015 mitteilte, damit habe sich eine neue Ausgangslage ergeben. Seine Niederlassungsbewilligung sei wegen Landesabwesenheit gestützt auf Art. 61 Abs. 2 AuG (heute AIG) spätestens am 15. Mai 2014 erloschen. Zudem skizzierte der Rechtsdienst den weiteren Verfahrensablauf in dem Sinne, dass das hängige Widerrufsverfahren wegen Gegenstandslosigkeit abzuschreiben und die Sache an die Sektion Aufenthalt (des MIKA, nachfolgend Sektion) zurückzuweisen wäre. Letzere hätte unter anderem das Erlöschen der Niederlassungsbewilligung festzustellen und über eine allfällige Wiederzulassung von A._ (Erteilung Aufenthaltsbewilligung) zu befinden. Mit Eingabe vom 31. Juli 2015 an das MIKA bestritt A._ das Erlöschen seiner Niederlassungsbewilligung und beantragte unter anderem die Aufhebung der Widerrufsverfügung vom 28. Oktober 2013 ohne Rückweisung an die Sektion, eventualiter die Aufrechterhaltung der Niederlassungsbewilligung während vier Jahren trotz Auslandaufenthalts. Falls die Niederlassungsbewilligung tatsächlich erloschen sei, werde zudem gestützt auf die Ausführungen ein Gesuch um Wiederzulassung gestellt. Mit Stellungnahme vom 17. August 2015 an den Rechtsdienst des MIKA (nachfolgend Rechtsdienst) teilte die Sektion mit, sie sei unter der Voraussetzung der Zustimmung des Rechtsdienstes bereit, die angefochtene Verfügung wiedererwägungsweise aufzuheben und einen neuen Sachentscheid betreffend Erlöschen der Niederlassungsbewilligung und Wiederzulassung zu fällen. Mit Verfügung vom 24. August 2015 hielt der Rechtsdienst unter anderem fest, es sei vorgesehen, das Einspracheverfahren als gegenstandslos abzuschreiben, wobei in Klammer "wiedererwägungsweise Aufhebung der angefochtenen Verfügung durch die Sektion mit Zustimmung des Rechtsdienstes als Rechtsmittelinstanz; § 2 Abs. 1 EGAR in Verbindung mit § 39 Abs. 1 VRPG" erwähnt wurde. Am 9. September 2015 verfügte der Rechtsdienst, das Einspracheverfahren werde als gegenstandslos abgeschrieben (Dispositiv), wobei in der Begründung ausgeführt wurde, damit gelte die angefochtene Verfügung als wiedererwägungsweise aufgehoben (E. 4.2 Abschreibungsverfügung).
B.b. Am 17. November 2015 stellte die Sektion A._ die verfügungsweise Feststellung des Erlöschens der Niederlassungsbewilligung und Wegweisung aus der Schweiz in Aussicht und gewährte ihm das rechtliche Gehör. Daraufhin beantragte A._ mit Eingabe vom 30. Dezember 2015, auf den Erlass einer Verfügung sei zu verzichten, da die Niederlassungsbewilligung nach wie vor gültig sei. Eventualiter sei die Niederlassungsbewilligung aufrechtzuerhalten oder infolge Wiederzulassung zu erteilen. Am 29. Januar 2016 verfügte die Sektion, die Niederlassungsbewilligung von A._ sei erloschen und der Genannte werde aus der Schweiz weggewiesen. Er habe die Schweiz innert 60 Tagen ab Rechtskraft der Verfügung zu verlassen. Die dagegen gerichtete Einsprache blieb gemäss Einspracheentscheid des Rechtsdienstes vom 1. November 2016 (nachfolgend Einspracheentscheid) erfolglos. Die daraufhin eingereichte Beschwerde vom 2. Dezember 2016 wies das Verwaltungsgericht des Kantons Aargau mit Urteil vom 27. März 2018 ab.
C.
Mit Beschwerde vom 7. Mai 2018 an das Bundesgericht, welche als Beschwerde in öffentlich-rechtlichen Angelegenheiten und als subsidiäre Verfassungsbeschwerde entgegenzunehmen sei, beantragt A._ (Beschwerdeführer) die Aufhebung des vorinstanzlichen Urteils, die Aufhebung des Einspracheentscheides vom 1. November 2016 und die Bestätigung des Bestandes der Niederlassungsbewilligung. Eventuell sei die Niederlassungsbewilligung aufrechtzuerhalten oder infolge Wiederzulassung zu erteilen bzw. das Migrationsamt dazu anzuweisen. Subeventuell sei die Aufenthaltsbewilligung zu erteilen bzw. das Migrationsamt dazu anzuweisen. Zudem beantragt der Beschwerdeführer für das bundesgerichtliche Verfahren und die genannten kantonalen Verfahren die unentgeltliche Rechtspflege.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen einen kantonal letztinstanzlichen Endentscheid betreffend den Widerruf oder die Feststellung des Erlöschens der Niederlassungsbewilligung ist zulässig, da auf den Fortbestand dieser Bewilligung ein Rechtsanspruch besteht (<ref-ruling> E. 1.2.1 S. 4; Art. 82 lit. a, Art. 83 lit. c Ziff. 2 e contrario, Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG).
1.2. Die Vorinstanz kommt unter anderem zum Schluss, dass dem Beschwerdeführer auch gestützt auf Art. 30 Abs. 1 lit. k (Wiederzulassung) und lit. b (schwerwiegender persönlicher Härtefall) AIG kein Aufenthaltsrecht zu gewähren sei. Diesbezüglich handelt es sich um Ermessensbewilligungen, deren Verweigerung nicht mit Beschwerde in öffentlich-rechtlichen Angelegenheiten angefochten werden kann (<ref-law>; Urteil 2C_866/2017 vom 7. März 2018 E. 1.1 mit Hinweisen). Jedoch steht dafür die subsidiäre Verfassungsbeschwerde offen, sofern Rügen bezüglich verfahrensrechtlicher Punkte erhoben werden, deren Verletzung einer formellen Rechtsverweigerung gleichkommt und die das Gericht von der Bewilligungsfrage getrennt beurteilen kann. Unzulässig sind dagegen Rügen, welche im Ergebnis wiederum auf eine materielle Überprüfung des angefochtenen Entscheids über die Ermessensbewilligung hinauslaufen, wie die Behauptung, die Vorinstanz habe sich nicht oder in willkürlicher Weise mit den Argumenten der Partei auseinandergesetzt ("Star"-Praxis; <ref-ruling> E. 2 und 4 S. 308, 311 f.; <ref-ruling> E. 1 S. 26 f. [zum OG]; <ref-ruling> E. 3c S. 312 f. [zum OG]; Urteil 2C_886/2017 vom 7. März 2018 E. 1.1). Zulässig ist wiederum die Rüge der vollständig fehlenden Begründung (<ref-ruling> E. 1.3 S. 269 f.; <ref-ruling> E. 2 S. 58) oder die Rüge der auf kantonaler Ebene überhaupt fehlenden Rechtsmittelmöglichkeit (<ref-ruling> E. 4.2 und 4.3 S. 132 f.; HANSJÖRG SEILER, in: Bundesgerichtsgesetz (BGG), 2. Aufl. 2015, N. 9 f. zu <ref-law>).
1.3. Vorliegend rügt der Beschwerdeführer im Zusammenhang mit der Ermessensbewilligung im Wesentlichen, die Vorinstanz habe sich mit seinen Argumenten überhaupt nicht auseinandergesetzt, weshalb sie die Begründungspflicht und das rechtliche Gehör im Sinne von <ref-law> und Art. 6 Ziff. 1 EMRK verletze und eine willkürliche Beweiswürdigung (<ref-law>) begehe. Die Vorinstanz hat jedoch im Rahmen von Art. 30 Abs. 1 lit. b und k AIG eine Interessenabwägung vorgenommen und die Verweigerung der Ermessensbewilligung begründet. Somit steht diesbezüglich die subsidiäre Verfassungsbeschwerde nicht offen.
1.4. Die Sachurteilsvoraussetzungen sind damit lediglich erfüllt, soweit die Beschwerde als solche in öffentlich-rechtlichen Angelegenheiten entgegengenommen werden kann. In diesem Rahmen ist auf sie einzutreten. Soweit sich die Beschwerde gegen die Verweigerung der Ermessensbewilligung (Art. 30 Abs. 1 lit. b und k AIG) richtet, ist sie dagegen unzulässig und auf die entsprechende, subsidiäre Verfassungsbeschwerde ist demnach nicht einzutreten (<ref-law>).
1.5. Ebenfalls unzulässig ist die Beschwerde, soweit mit ihr die Aufhebung des Einspracheentscheides verlangt wird, da letzterer aufgrund des Devolutiveffekts durch das (vorinstanzliche) Urteil des Verwaltungsgerichts ersetzt wird. Anfechtungsobjekt vor Bundesgericht bildet einzig das vorinstanzliche Urteil, wobei die Verfügungen unterer Instanzen als inhaltlich mitangefochten gelten (<ref-ruling> E. 1.4 S. 144; Urteile 2C_432/2016 vom 26. Januar 2018 E. 1.1; 2C_578/2011 vom 1. Dezember 2011 E. 1.2). Auf die Beschwerde ist demzufolge, soweit sie sich gegen den Einspracheentscheid richtet, nicht einzutreten.
2.
2.1. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 (in erster Linie Bundes- und Völkerrecht) und 96 BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), prüft jedoch unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG) nur die geltend gemachten Rechtsverletzungen, sofern rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.5 S. 144). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 2.2 S. 232; <ref-ruling> E. 2.5 S. 314). Der Eingriff in kantonales oder kommunales Recht bildet nur insofern einen eigenständigen Beschwerdegrund, als die Verletzung kantonaler verfassungsmässiger Rechte oder kantonaler Bestimmungen zum Stimm- und Wahlrecht geltend gemacht wird (Art. 95 lit. c und d BGG). Abgesehen davon kann das Bundesgericht die Auslegung und Anwendung kantonalen Verfassungs-, Gesetzes- oder Verordnungsrechts lediglich daraufhin überprüfen, ob dadurch Bundes-, Völker- oder interkantonales Recht verletzt wird (Art. 95 lit. a, b und e BGG). Dabei steht die Verletzung des Willkürverbots (<ref-law>) im Vordergrund (<ref-ruling> E. 3.3 S. 166; <ref-ruling> E. 2.5.2 S. 250).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Eine Berichtigung oder Ergänzung der vorinstanzlichen Sachverhaltsfeststellungen ist von Amtes wegen (<ref-law>) oder auf Rüge hin (<ref-law>) möglich. Von den tatsächlichen Grundlagen des vorinstanzlichen Urteils weicht das Bundesgericht jedoch nur ab, wenn diese offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law>; <ref-ruling> E. 1.6 S. 144 f.).
Zur Sachverhaltsfeststellung gehört auch die auf Indizien gestützte Beweiswürdigung. Die Sachverhaltsfeststellung bzw. Beweiswürdigung erweist sich als willkürlich gemäss <ref-law>, wenn sie offensichtlich unhaltbar oder aktenwidrig ist, 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 (<ref-ruling> E. 2.3 S. 265 f.; Urteile 2C_1072/2014 vom 9. Juli 2015 E. 1.4; 2C_310/2014 vom 25. November 2014 E. 1.2). Eine entsprechende Rüge ist substanziiert vorzubringen; auf rein appellatorische Kritik an der Sachverhaltsfeststellung bzw. Beweiswürdigung geht das Gericht nicht ein (<ref-ruling> E. 2.3 S. 266; <ref-ruling> E. 10.1 S. 444 f.).
3.
3.1. Der Beschwerdeführer rügt, die Vorinstanz habe in Bezug auf seine Vorbringen gegenüber der genannten Abschreibungsverfügung vom 9. September 2015 durch den blossen pauschalen und unpräzisen Verweis auf den Einspracheentscheid die Begründungspflicht und das rechtliche Gehör im Sinne von <ref-law> und Art. 6 Ziff. 1 EMRK verletzt und begehe eine willkürliche Beweiswürdigung.
3.2. Gemäss der aus dem Anspruch auf rechtliches Gehör (<ref-law>) fliessenden Begründungspflicht soll die Urteilsbegründung dem Betroffenen ermöglichen, die Tragweite des Entscheides zu erfassen und diesen in Kenntnis der Überlegungen des Gerichts anzufechten. Die Begründungspflicht verlangt jedoch nicht, dass sich das Gericht mit sämtlichen vorgebrachten Sachverhaltselementen, Beweismitteln und Rügen auseinandersetzt. Vielmehr kann es sich auf die wesentlichen Überlegungen, welche zum Entscheid geführt haben, beschränken, selbst wenn diese fehlerhaft sind (<ref-ruling> E. 5.2 S. 70 f.; <ref-ruling> E. 3.2.4 S. 31; <ref-ruling> E. 5.1 S. 238 mit Hinweisen; <ref-ruling> E. 3.3 S. 445). Die Begründungspflicht ist nur dann verletzt, wenn das Gericht auf die für den Ausgang des Verfahrens wesentlichen Vorbringen selbst implizit nicht eingeht (<ref-ruling> E. 5.2 S. 248 f.). Wenn eine Rechtsmittelinstanz ihr Urteil durch Verweis auf Urteilserwägungen der unteren Instanz begründet, ist dies mit dem Anspruch auf rechtliches Gehör vereinbar, sofern mit dem Rechtsmittel keine erheblichen Einwände vorgebracht werden, mit denen sich der unterinstanzliche Entscheid nicht bereits auseinandersetzte und die geeignet wären, es in Frage zu stellen. Umgekehrt ist es verfassungswidrig, wenn die Rechtsmittelinstanz trotz neuer, erheblicher Einwände, welche nicht Gegenstand des unterinstanzlichen Entscheides waren, auf eine eigene Begründung verzichtet und bloss auf den unterinstanzlichen Entscheid verweist (<ref-ruling> E. 3a S. 409 f.; Urteil 1P.69/2004 vom 7. April 2004 E. 1.1.3 und 1.1.4; vgl. Urteil 6B_651/2018 vom 17. Oktober 2018 E. 8.3.1 und 8.4).
3.3. Wie sich aus den E. 2 und 3 des Einspracheentscheides ergibt, hat sich bereits die untere Instanz bzw. der Rechtsdienst des MIKA mit den verfahrensmässigen Vorbringen gegenüber dem Widerrufsverfahren, der Abschreibungsverfügung und der anschliessenden Feststellung des Erlöschens der Niederlassungsbewilligung auseinandergesetzt. Die Beschwerde an die Vorinstanz enthält diesbezüglich keine neuen, erheblichen Einwände. Der Verweis der Vorinstanz in E. 2 ihrer Urteilsbegründung auf die Begründung des Einspracheentscheides erweist sich damit als verfassungskonform und verstösst nicht gegen den Anspruch auf rechtliches Gehör.
3.4. Inwieweit die diesbezügliche, vorinstanzliche Beweiswürdigung willkürlich sein soll, legt der Beschwerdeführer nicht substanziiert dar, sondern übt appellatorische Kritik an der vorinstanzlichen Sachverhaltsfeststellung, weshalb darauf nicht einzutreten ist.
4.
4.1. Im Weiteren macht der Beschwerdeführer im Wesentlichen geltend, aufgrund der wiedererwägungsweisen Aufhebung der Widerrufsverfügung vom 28. Oktober 2013 durch die Abschreibungsverfügung des Rechtsdienstes vom 9. September 2015, ohne dass in letzterer das Erlöschen der Niederlassungsbewilligung festgestellt worden sei, sei das Widerrufsverfahren rechtskräftig beendet worden. Er (der Beschwerdeführer) verfüge deshalb immer noch über die Niederlassungsbewilligung. Nach Ansicht des Beschwerdeführers hätte der Rechtsdienst in seiner Abschreibungsverfügung beschwerdefähig das Erlöschen der Niederlassungsbewilligung oder die Rückweisung der Sache an die Sektion beschliessen können und müssen. Ausserdem sei der Beschwerdeführer mangels Beschwer nicht gehalten gewesen, die Abschreibungsverfügung anzufechten. Mit ihrem Vorgehen hätten die Migrationsbehörden kantonales Recht willkürlich angewendet. § 39 Abs. 2 des Gesetzes des Kantons Aargau vom 4. Dezember 2007 über die Verwaltungsrechtspflege (VRPG AG; SAR 271.200) erlaube, wenn ein Rechtsmittelentscheid vorliege, die Wiedererwägung nur dann, wenn sich der dem rechtskräftigen Entscheid zugrunde liegende Sachverhalt oder die Rechtslage erheblich und entscheidrelevant geändert hätten.
4.2. Vorliegend existierte jedoch zum Zeitpunkt der Wiedererwägung am 9. September 2015 noch kein Rechtsmittelentscheid. Dieser erging erst am 1. November 2016, und zwar in einem anderen Verfahren als dem Widerrufsverfahren (nämlich im Feststellungsverfahren bezüglich Erlöschen der Niederlassungsbewilligung), durch den Einspracheentscheid. Wenn der Beschwerdeführer die willkürliche Anwendung von § 39 Abs. 2 VRPG AG rügt, kann ihm somit mangels Anwendungsfall nicht gefolgt werden. Weitere substanziierte Rügen enthält die Beschwerde in diesem Zusammenhang nicht. Jedenfalls legt der Beschwerdeführer nicht dar, welche rechtlichen Bestimmungen durch das gewählte Verfahren der Migrationsbehörden verletzt worden sein sollen, noch begründet er substanziiert, inwiefern kantonales Recht willkürlich angewendet worden sein soll, weshalb darauf nicht weiter einzugehen ist.
5.
5.1. In der Sache bringt der Beschwerdeführer vor, einzig aufgrund der Untersuchungshaft im Ausland vom mehr als sechs Monaten könne die Niederlassungsbewilligung bei verfassungskonformer Anwendung von Art. 61 Abs. 2 AuG nicht erloschen sein, da es ihm absolut unmöglich und nicht zumutbar gewesen sei, sich anders zu verhalten. Der Beschwerdeführer rügt damit sinngemäss eine Verletzung von Art. 61 Abs. 2 AuG (seit 1. Januar 2019 inhaltlich unverändert <ref-law>).
5.2. Gemäss <ref-law> erlischt die Niederlassungsbewilligung, wenn sich die ausländische Person ohne Abmeldung während sechs Monaten im Ausland aufhält und vor Ablauf der sechsmonatigen Frist kein Gesuch um Aufrechterhaltung derselben eingereicht hat (Art. 79 Abs. 2 Verordnung über die Zulassung, Aufenthalt und Erwerbstätigkeit vom 24. Oktober 2007 [VZAE; SR 142.201]). Gemäss gefestigter bundesgerichtlicher Rechtsprechung kommt es weder auf die Motive der Landesabwesenheit noch auf die Absichten des Betroffenen an (Urteile 2C_2/2018 vom 15. Mai 2018 E. 1.1 mit Hinweisen; 2C_19/2017 vom 21. September 2017 E. 4.1; 2C_405/2015 vom 23. Oktober 2015 E. 2.2). Auch eine Inhaftierung im Ausland führt zum Erlöschen der Niederlassungsbewilligung (Urteile 2C_512/2013 vom 17. Februar 2014 E. 2; 2C_461/2012 vom 7. November 2012 E. 2.4.1). Der Beschwerdeführer bringt vor, es müsse zwischen Strafvollzug und Untersuchungshaft differenziert werden. Wenn es jedoch keine Rolle spielt, ob sich die betroffene Person unfreiwillig im Ausland befindet, muss auch nicht danach differenziert werden, ob es sich um Haft im Rahmen des regulären Strafvollzugs oder um Untersuchungshaft handelt. Ebenso wenig muss der unfreiwilligen Landesabwesenheit ein vorwerfbares, strafbares Verhalten der betroffenen Person zugrunde liegen, um die Rechtsfolge von <ref-law> auszulösen (vgl. Urteil 2C_461/2012 vom 7. November 2012 E. 2.4.1). Im vom Beschwerdeführer zitierten Urteil 2C_776/2017 vom 2. Oktober 2017 hat das Bundesgericht denn auch die Rechtsfolge von <ref-law> auf den Fall einer sechsmonatigen Untersuchungshaft angewendet. Ob die Untersuchungshaft mit einer Verurteilung (wie im Urteil 2C_776/2017) oder wie vorliegend mit einer Einstellung mangels nachweisbarem strafrechtlichem Vorwurf abgeschlossen wird, spielt keine Rolle. Die vorinstanzliche Anwendung von <ref-law> erweist sich damit als bundesrechtskonform.
5.3. Dass die Vorinstanz sich nicht mit dem Argument des Beschwerdeführers, wonach zwischen Strafvollzug und Untersuchungshaft zu differenzieren sei, auseinandergesetzt hat, führt nicht zu einer Verletzung der Begründungspflicht bzw. des Anspruchs auf rechtliches Gehör, da das Gericht sich nicht mit sämtlichen Vorbringen auseinandersetzen muss, sondern sich auf die entscheidwesentlichen Punkte beschränken kann (vgl. E. 3.2 oben). Ob die betroffene Person sich im Ausland im Strafvollzug oder in Untersuchungshaft ohne anschliessende Verurteilung befand, ist wie dargelegt in Bezug auf <ref-law> nicht entscheidrelevant.
5.4. Im Übrigen hat die Vorinstanz mangels substanziierter Sachverhaltsrüge sachverhaltsmässig verbindlich festgestellt, dass es dem Beschwerdeführer möglich gewesen wäre, während der Untersuchungshaft ein Gesuch um Aufrechterhaltung der Niederlassungsbewilligung zu stellen. Dass die Vorinstanz entgegen dem Beschwerdeführer unter Beachtung bestimmter Voraussetzungen, welche auch hier erfüllt sind, diesbezüglich zur Begründung auf die Erwägungen der unteren Instanz verweisen kann, ohne dass die Begründungspflicht bzw. der Anspruch auf rechtliches Gehör verletzt ist, ergibt sich ebenfalls aus E. 3.2 oben.
6.
6.1. Der Beschwerdeführer rügt im Weiteren eine Verletzung des Rechts auf Achtung des Familienlebens gemäss Art. 8 EMRK bzw. <ref-law>, da unter anderem seine vier Kinder mit einem gefestigten Aufenthaltsrecht in Genf bei ihrer Mutter lebten.
6.2. Art. 8 EMRK verschafft keinen Anspruch auf Aufenthalt in einem bestimmten Staat. Dennoch kann es das in Art. 8 EMRK geschützte Recht auf Achtung des Familienlebens verletzen, wenn einer ausländischen Person, deren Familienangehörige sich hier aufhalten und über ein gefestigtes Aufenthaltsrecht verfügen, die Anwesenheit untersagt und damit ihr Zusammenleben vereitelt wird (<ref-ruling> E. 4.2 S. 96; <ref-ruling> E. 5.1 S. 26; <ref-ruling> E. 6.1 S. 46 mit Hinweisen; <ref-ruling> E. 1.3.1 S. 145 f.; Urteil 2C_1009/2018 vom 30. Januar 2019 E. 3.1). Art. 8 EMRK bzw. <ref-law> schützt in diesem Zusammenhang in erster Linie die Kernfamilie, d.h. die Gemeinschaft der Ehegatten bzw. Eltern mit ihren minderjährigen Kindern (BGE <ref-ruling> E. 1.3.2 S. 146; Urteile 2C_293/2018 vom 5. Oktober 2018 E. 1.4; 2C_301/2016 vom 19. Juli 2017 E. 5).
6.3. Der vorinstanzliche Entscheid hält fest, Art. 8 EMRK sei nicht tangiert und verweist diesbezüglich auf E. 10 des Einspracheentscheides. Dieser führt lediglich aus, in der Schweiz lebten keine nahen Angehörigen des Beschwerdeführers, weshalb eine Berufung auf Art. 8 EMRK ausser Betracht falle. An anderer Stelle hält der Einspracheentscheid (E. 3.3) jedoch fest, C._ habe am 10. Februar 2016 bei den Genfer Migrationsbehörden ein Familiennachzugsgesuch für ihre vier Kinder gestellt, welches gemäss weiteren Ausführungen am 31. Mai 2016 noch hängig war, wobei die Genfer Behörden eine Ablehnung in Aussicht stellten. Aus den Akten ergibt sich, dass zumindest am 15. April 2016 die Kinder immer noch beim Beschwerdeführer in U._ wohnten. Der vorinstanzliche Entscheid, welcher vom 27. März 2018 datiert, enthält dazu keine weiteren Sachverhaltsfeststellungen, obwohl in der Beschwerde an die Vorinstanz geltend gemacht wurde, entgegen dem Einspracheentscheid lebten die vier Kinder mit einer Aufenthaltsbewilligung bei ihrer Mutter in Genf. Auch wenn der Untersuchungsgrundsatz im Ausländerrecht durch die Mitwirkungspflicht relativiert wird (<ref-law>), wäre es bei dieser Ausgangslage seitens der Vorinstanz geboten gewesen, den neuesten Stand des Aufenthaltsstatus der Kinder abzuklären und sachverhaltsmässig festzustellen. Dies rechtfertigt sich insbesondere angesichts des Umstandes, dass die Aargauer und Genfer Migrationsbehörden bereits Informationen zum vorliegenden Fall austauschten und die Genfer Migrationsbehörden wohl über noch exaktere Informationen zum Aufenthaltsstatus der Kinder in ihrem Kanton verfügen als der Beschwerdeführer (vgl. zum Verhältnis Mitwirkungspflicht und Untersuchungsgrundsatz <ref-ruling> E. 5 S. 67 ff.; <ref-ruling> E. 6.3.1 S. 298 f.; Urteil 2C_866/2017 vom 7. März 2018 E. 3.1.2).
6.4. Die Sache erweist sich damit, was die Rüge betreffend Art. 8 EMRK betrifft, als nicht entscheidungsreif. Sie wird deshalb zur ergänzenden Sachverhaltsabklärung und -feststellung an die Vorinstanz zurückgewiesen. Sollte sich ergeben, dass Kinder des Beschwerdeführers in der Schweiz über ein gefestigtes Aufenthaltsrecht verfügen, wird die Vorinstanz eine Interessenabwägung im Rahmen von Art. 8 EMRK vornehmen müssen. In deren Rahmen wird die Vorinstanz dem Beschwerdeführer das Verheimlichen der Beziehung zu C._ nicht vorwerfen können, denn dass der Beschwerdeführer mit C._ über mindestens drei gemeinsame Kinder verfügt, war den Behörden seit dem 30. November 2007, anlässlich der Umwandlung seiner Aufenthaltsbewilligung in eine Niederlassungsbewilligung, bekannt (vgl. Sachverhalt lit. A.a oben).
7.
7.1. Die Beschwerde ist gutzuheissen und der angefochtene Entscheid aufzuheben. Die Sache geht zurück an die Vorinstanz zu neuem Entscheid im Sinne der Erwägungen.
7.2. Bei diesem Ausgang des Verfahrens erweist sich das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren als gegenstandslos. Für letzteres sind keine Gerichtskosten zu erheben (<ref-law>). Hingegen hat der Kanton Aargau den obsiegenden Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG), wobei die Entschädigung direkt an seinen Rechtsvertreter auszurichten ist.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und das Urteil des Verwaltungsgerichts des Kantons Aargau, 2. Kammer, vom 27. März 2018 wird aufgehoben. Die Sache wird zu neuem Entscheid im Sinne der Erwägungen an die Vorinstanz zurückgewiesen.
2.
Für das bundesgerichtliche Verfahren werden keine Gerichtskosten erhoben.
3.
Der Kanton Aargau hat den Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Aargau, 2. Kammer, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 1. Mai 2019
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Quinto