Sachverhalt:
A.
X._ lebt getrennt von seiner ehemaligen Lebenspartnerin A._. Die beiden gemeinsamen Kinder wohnten bis am 15. Oktober 2011 bei der Mutter, wobei die Eltern die gemeinsame elterliche Sorge innehatten. Die Staatsanwaltschaft IV des Kantons Zürich wirft X._ vor, die Kinder am 15. Oktober 2011 im Rahmen seines Besuchsrechts abgeholt zu haben, mit ihnen ohne Wissen und Zustimmung der Mutter sowie der Beiständin nach Nigeria gereist zu sein und sie dort bei Familienangehörigen zurückgelassen zu haben. Dies in der Absicht, die Kinder dort aufziehen zu lassen, bis ihm durch die schweizerischen Behörden die alleinige elterliche Sorge übertragen werde.
B.
In Bestätigung des Urteils des Bezirksgerichts Zürich vom 3. Juni 2013 sprach das Obergericht des Kantons Zürich X._ am 13. Januar 2014 der mehrfachen qualifizierten Freiheitsberaubung und des mehrfachen Entziehens von Minderjährigen schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von sieben Jahren. Zudem entschied es über den Widerruf einer bedingt ausgesprochenen Geldstrafe und die Zivilforderungen von A._.
Das Bundesgericht hiess die Beschwerde in Strafsachen von X._ am 2. Dezember 2014 teilweise gut, hob das Urteil des Obergerichts vom 13. Januar 2014 auf und wies die Sache zur neuen Entscheidung an dieses zurück (Verfahren 6B_123/2014). Das Bundesgericht erwog unter anderem, der Tatbestand der Freiheitsberaubung sei nicht erfüllt. Demgegenüber seien die objektiven Tatbestandsmerkmale der Entführung gemäss <ref-law> gegeben. Ob dieser Tatbestand auch in subjektiver Hinsicht erfüllt sei, müsse die Vorinstanz nach ergänzter Sachverhaltsfeststellung beurteilen.
C.
Mit Urteil vom 21. Oktober 2015 stellte das Obergericht unter anderem fest, dass sein Urteil vom 13. Januar 2014 hinsichtlich des Schuldspruchs wegen mehrfachen Entziehens von Minderjährigen in Rechtskraft erwachsen war. Es verurteilte X._ wegen mehrfacher qualifizierter Entführung zu einer Freiheitsstrafe von sieben Jahren und widerrief den mit seinem Urteil vom 8. Juni 2012 gewährten bedingten Strafvollzug. Ferner stellte es fest, dass X._ A._ dem Grundsatze nach schadenersatzpflichtig ist, und verpflichtete ihn, ihr eine zu verzinsende Genugtuung von Fr. 30'000.-- zu bezahlen. Es auferlegte die Kosten des ersten Berufungsverfahrens X._, wobei es die Kosten der amtlichen Verteidigung sowie der unentgeltlichen Verteidigung von A._ einstweilen auf die Gerichtskasse nahm und die Rückzahlungspflicht im Sinne von <ref-law> vorbehielt.
D.
X._ beantragt mit Beschwerde in Strafsachen, das Urteil des Obergerichts vom 21. Oktober 2015 sei vollumfänglich aufzuheben und er sei vom Vorwurf der mehrfachen qualifizierten Entführung freizusprechen. Eventualiter sei er, unter Anrechnung der erstandenen Haft, mit einer Freiheitsstrafe von maximal 42 Monaten zu bestrafen. Der Kanton Zürich sei zu verpflichten, ihm eine Genugtuung von mindestens Fr. 120.-- pro Tag Überhaft und eine Entschädigung von Fr. 15'000.-- zu bezahlen. Die Genugtuung für A._ sei auf Fr. 10'000.-- zu reduzieren und die Kosten ihrer unentgeltlichen Verbeiständung seien definitiv dem Kanton Zürich aufzuerlegen. Subeventualiter sei die Sache zur neuen Entscheidung an das Obergericht zurückzuweisen. Ferner ersucht er um unentgeltliche Rechtspflege und Verbeiständung.

Erwägungen:
1.
Nicht zu hören ist der Beschwerdeführer mit seinen persönlichen Eingaben vom 9. resp. 16. Dezember 2015 (Postaufgabe: 18. Dezember 2015), vom 24. Februar 2016 und vom 8. März 2016. Das begründete vorinstanzliche Urteil ging seinem Verteidiger am 12. November 2015 zu. Die 30-tägige Frist zur Einreichung der Beschwerde begann am 13. November 2015 und endete am 12. Dezember 2015 (vgl. <ref-law>). Damit sind die Eingaben des Beschwerdeführers verspätet.
2.
2.1. Der Beschwerdeführer rügt im Zusammenhang mit dem Schuldspruch wegen mehrfacher qualifizierter Entführung eine offensichtlich unrichtige Feststellung des subjektiven Sachverhalts. Indem die Vorinstanz seine Beweisanträge ablehne und davon ausgehe, er habe gewusst, dass er den Interessen sowie dem Wohl seiner Kinder in krasser Art und Weise zuwiderhandle, indem er sie nach Nigeria verbringe, und habe die negativen Folgen für seine Kinder mindestens billigend in Kauf genommen, verletze sie seinen Anspruch auf rechtliches Gehör (<ref-law>), das Willkürverbot (<ref-law>) und den Grundsatz "in dubio pro reo".
2.2. Die Vorinstanz erwägt, das Bundesgericht habe in seinem Rückweisungsentscheid verbindlich entschieden, dass die objektiven Tatbestandsmerkmale der Entführung gemäss <ref-law> gegeben seien, weshalb sie nur noch zu prüfen habe, ob der Beschwerdeführer den Tatbestand auch in subjektiver Hinsicht erfülle. Davon sei gestützt auf dessen Aussagen auszugehen. Daraus ergebe sich, dass er in Kenntnis der schweizerischen Rechtslage betreffend Familienname seiner Söhne, elterlicher Sorge und Obhut gehandelt habe. Aus seinen Äusserungen gehe hervor, dass er seine Kinder nicht zu ihrem Wohl nach Nigeria verbracht habe. Vielmehr habe er gegenüber der Kindsmutter sowie den schweizerischen Behörden zum Ausdruck bringen sowie erreichen wollen, dass das Sorgerecht ihm zustehe und er nicht daran denke, sich an Entscheide der schweizerischen Behörden zu halten. Soweit er geltend mache, er habe die Kinder nach Nigeria gebracht, um sie von den Drogengeschäften ihrer Mutter zu schützen, müsse davon ausgegangen werden, dass dieses Motiv im Hintergrund stehe bzw. es sich um eine Schutzbehauptung handle. Zusammengefasst habe der Beschwerdeführer gewusst, dass er mit seinem Vorgehen die Interessen und das Wohl seiner Kinder in krasser Art sowie Weise verletze. Indem er trotzdem gehandelt habe, habe er solch massiv negative Folgen für seine Kinder mindestens billigend in Kauf genommen. Mit seinem Handeln habe er seine Interessen über diejenigen seiner Kinder gestellt. Es sei ihm letztlich bloss darum gegangen, aus egoistischer Motivation seine Macht gegenüber der Kindsmutter und den Behörden in Selbstjustiz durchzusetzen. Da sich dies bereits aus seinen Aussagen ergebe, sei es nicht erforderlich, weitere Beweise abzunehmen (Urteil S. 9 ff.).
2.3.
2.3.1. Das Bundesgericht hielt in seinem Entscheid vom 2. Dezember 2014 zum objektiven Tatbestand von <ref-law> fest, dass grundsätzlich jeder Elternteil, der das Recht hat, über den Aufenthaltsort des Kindes zu bestimmen, berechtigt ist, diesen zu verändern, ohne eine Entführung zu begehen. Greift die Verbringung des Kindes an einen anderen Ort jedoch massiv in dessen Interessen ein, lässt sich die Tat nicht mit dem Aufenthaltsbestimmungsrecht rechtfertigen (<ref-ruling> E. 4.5.5 S. 19). In subjektiver Hinsicht setzt der Tatbestand der Entführung Vorsatz voraus, wobei Eventualvorsatz genügt (vgl. DELNON/RÜDY, in: Basler Kommentar, Strafrecht, Bd. II, 3. Aufl. 2013, N. 57 zu <ref-law>). Nach ständiger Rechtsprechung ist Eventualvorsatz gegeben, wenn der Täter den Eintritt des Erfolgs bzw. die Verwirklichung des Tatbestands für möglich hält, aber dennoch handelt, weil er den Erfolg für den Fall seines Eintritts in Kauf nimmt (<ref-law>), sich mit ihm abfindet, mag er ihm auch unerwünscht sein (<ref-ruling> E. 4.2.3 S. 4 mit Hinweis). Vorliegend ist daher zu prüfen, ob der Beschwerdeführer es zumindest für möglich hielt und in Kauf nahm, dass die Verbringung seiner Kinder nach Nigeria massiv in deren Interessen sowie Wohl eingreift.
Das Gericht darf vom Wissen des Täters auf den Willen schliessen, wenn sich dem Täter der Eintritt des Erfolgs als so wahrscheinlich aufdrängte, dass die Bereitschaft, ihn als Folge hinzunehmen, vernünftigerweise nur als Inkaufnahme des Erfolgs ausgelegt werden kann (<ref-ruling> E. 4.2.3 S. 4; <ref-ruling> E. 3.2.2 S. 28 f.; je mit Hinweisen). Je grösser die Wahrscheinlichkeit der Tatbestandsverwirklichung ist und je schwerer die Rechtsgutsverletzung wiegt, desto näher liegt die Schlussfolgerung, der Täter habe die Tatbestandsverwirklichung in Kauf genommen (<ref-ruling> E. 2.3.2 S. 17; <ref-ruling> E. 5.3 S. 226).
Was der Täter weiss, will und in Kauf nimmt, betrifft eine innere Tatsache und ist Tatfrage. Rechtsfrage ist hingegen, ob gestützt auf die festgestellten Tatsachen bewusste Fahrlässigkeit, Eventualvorsatz oder direkter Vorsatz gegeben ist (<ref-ruling> E. 4.2.3 S. 4 mit Hinweis).
2.3.2. Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Offensichtlich unrichtig ist die Feststellung des Sachverhalts, wenn sie willkürlich ist (<ref-ruling> E. 10.1 S. 445 mit Hinweisen; zum Begriff der Willkür <ref-ruling> E. 1.2 S. 308 f.; <ref-ruling> E. 2.1 S. 18 f.; je mit Hinweisen). Dem Grundsatz "in dubio pro reo" kommt in der vom Beschwerdeführer angerufenen Funktion als Beweiswürdigungsregel im Verfahren vor Bundesgericht keine über das Willkürverbot von <ref-law> hinausgehende selbstständige Bedeutung zu (<ref-ruling> E. 7 S. 82 mit Hinweisen).
Das Gericht kann, ohne den Anspruch auf rechtliches Gehör (Art. 3 Abs. 2 lit. c und Art. 107 StPO sowie <ref-law>) zu verletzen, einen Beweisantrag ablehnen, wenn es in willkürfreier Würdigung der bereits abgenommenen Beweise zur Überzeugung gelangt, der rechtlich erhebliche Sachverhalt sei genügend abgeklärt, und es überdies in willkürfreier antizipierter Würdigung der zusätzlich beantragten Beweise annehmen kann, seine Überzeugung werde dadurch nicht mehr geändert (vgl. <ref-law>; <ref-ruling> E. 3.3 S. 64; <ref-ruling> E. 5.3 S. 236 f. mit Hinweisen).
Die Rüge der Verletzung von Grundrechten (einschliesslich der Willkür bei der Sachverhaltsfeststellung) muss klar vorgebracht und substanziiert begründet werden. Auf eine rein appellatorische Kritik am angefochtenen Urteil tritt das Bundesgericht nicht ein (vgl. <ref-law>; <ref-ruling> E. 1.3.1 S. 253; <ref-ruling> E. 2.3 S. 266; je mit Hinweisen).
2.4.
2.4.1. Die Vorinstanz zeigt anhand der Aussagen des Beschwerdeführers ausführlich und überzeugend auf, weshalb sie zum Schluss gelangt, dass er seine Kinder nicht zu deren Wohl nach Nigeria verbrachte, sondern um das ihm seines Erachtens zustehende Sorgerecht zu erzwingen. Der Beschwerdeführer setzt sich mit dieser vorinstanzlichen Aussagewürdigung nur rudimentär auseinander und zeigt nicht auf, inwieweit sie offensichtlich unhaltbar sein soll sowie die Aussagen andere Schlussfolgerungen geradezu aufdrängen. Soweit er sich darauf beschränkt, seine Aussagen auszugsweise wiederzugeben und darzulegen, wie sie aus seiner Sicht richtigerweise zu würdigen wären, ohne sich detailliert mit den diesbezüglichen vorinstanzlichen Erwägungen auseinanderzusetzen, erschöpfen sich seine Ausführungen in einer appellatorischen Kritik. Darauf ist nicht einzutreten.
2.4.2. Hinsichtlich des Einwands des Beschwerdeführers, er habe seine Kinder nach Nigeria gebracht, um sie von den Drogengeschäften ihrer Mutter zu schützen, erwägt die Vorinstanz, er habe dies zwar regelmässig angegeben, eine genaue Analyse der hierzu deponierten Aussagen lasse jedoch darauf schliessen, dass dieses Motiv eindeutig im Hintergrund stehe. So habe er diesen Grund anlässlich der Berufungsverhandlung erst auf Nachfrage hin genannt. Aufgrund der zeitlichen Abläufe verfange das Argument der Verteidigung nicht, der Vorwurf des Beschwerdeführers sei keine Reaktion bzw. ein Gegenangriff auf das von der Kindsmutter gegen ihn in Gang gesetzte Strafverfahren. Vielmehr sei davon auszugehen, dass es sich tatsächlich um Schutzbehauptungen des Beschwerdeführers handle. Dazu passe, dass er in seinem Gesuch um Zuteilung der (alleinigen) elterlichen Sorge an die Vormundschaftsbehörde Zürich vom 27. Oktober 2009 den angeblichen Drogenhandel der Kindsmutter nicht erwähnt habe (Urteil S. 16 f.).
Was der Beschwerdeführer hiergegen vorbringt, ist nicht geeignet, die vorinstanzliche Beweiswürdigung willkürlich erscheinen zu lassen. Er wendet zwar zutreffend ein, dass vorliegend nicht zu prüfen ist, ob die Kindsmutter tatsächlich in Drogengeschäfte verwickelt gewesen sei, sondern, ob er hiervon überzeugt gewesen sei. Jedoch berücksichtigt die Vorinstanz zu Recht, dass auf seine Anzeige vom 11. Mai 2010 am 20. September 2010 nicht eingetreten wurde (Urteil S. 16; kantonale Akten, act. 333/2). Dieser Umstand hätte seine angebliche Überzeugung ein Jahr vor dem Verbringen der Kinder nach Nigeria zumindest relativieren müssen. Entgegen seinem Einwand ist aus seinen Aussagen und der Tatsache, dass er die Kindsmutter anzeigte, nicht zwingend zu schliessen, er sei davon ausgegangen, diese sei in Betäubungsmittelgeschäfte involviert. Angesichts der Chronologie der Ereignisse ist es nicht schlechterdings unhaltbar, wenn die Vorinstanz davon ausgeht, der Drogenvorwurf sei eine Reaktion auf das Verhalten der Kindsmutter gewesen. So verfügte die Kantonspolizei Zürich am 1. August 2009 aufgrund eines Vorfalls von häuslicher Gewalt im Sinne von § 2 des Gewaltschutzgesetzes des Kantons Zürich vom 19. Juni 2006 (GSG; LS 351) Schutzmassnahmen (Wegweisung, Rayon- und Kontaktverbot) nach § 3 GSG gegen den Beschwerdeführer (Urteil S. 16; kantonale Akten, act. 318/1). Der Einzelrichter in Strafsachen des Bezirks Pfäffikon verlängerte diese Schutzmassnahmen am 10. August 2009 bis zum 15. November 2009 (kantonale Akten, act. 318/2). Im November 2009 verliess die Kindsmutter mit den Kindern sodann die mit dem Beschwerdeführer gemeinsam bewohnte Wohnung (Urteil S. 16). Mit Schreiben vom 27. Oktober 2009 beantragte der Beschwerdeführer bei der Vormundschaftsbehörde Zürich die Zuteilung der (alleinigen) elterlichen Sorge an sich, ohne auf einen allfälligen Drogenhandel der Kindsmutter hinzuweisen (Urteil S. 16 f.; kantonale Akten, act. 17/3/37). Am 11. Mai 2010 verzeigte er diese wegen Drogenhandels, am 30. Juli 2010 wegen falscher Anschuldigung, Drohung und Nötigung. Auf beide Anzeigen trat die zuständige Staatsanwaltschaft nicht ein (Urteil S. 16; kantonale Akten, act. 318/3 und 333/2). Am 25. April 2010 und 12. Mai 2010 kam es zu weiteren Vorfällen, infolge derer der Beschwerdeführer vom Obergericht des Kantons Zürich am 8. Juni 2012 der Nötigung und der mehrfachen Tätlichkeiten zum Nachteil der Kindsmutter schuldig erklärt wurde (kantonale Akten, act. 12/9 ff., 17/3/7 ff., 17/3/28). Angesichts dieser zeitlichen Abfolge erscheint der Schluss der Vorinstanz, die Vorwürfe des Beschwerdeführers, die Kindsmutter handle mit Drogen, seien Schutzbehauptungen, nicht schlechterdings unhaltbar. Entgegen der Ansicht des Beschwerdeführers ist die vorinstanzliche Begründung schlüssig und nachvollziehbar. Schliesslich setzt er sich nicht mit der vorinstanzlichen (Alternativ-) Erwägung auseinander, aus seinen Aussagen ergebe sich, dass der angebliche Drogenhandel der Kindsmutter - sollte es sich hierbei nicht nur um eine Schutzbehauptung handeln - ein zweitrangiges Motiv für die Verbringung der Kinder nach Nigeria gewesen sei (vgl. Urteil S. 16).
Insgesamt vermag der Beschwerdeführer nicht aufzuzeigen, dass der vorinstanzliche Schluss offensichtlich unhaltbar ist, er habe gewusst, dass er die Interessen und das Wohl seiner Kinder in eklatanter Weise verletze, wenn er diese nach Nigeria an einen fremden Ort, zu ihnen unbekannten Personen, fernab von der Mutter verbringe, sowie habe diese Folge durch sein Handeln billigend in Kauf genommen.
2.4.3. Unbegründet ist auch die Rüge des Beschwerdeführers, die Vorinstanz verletze seinen Anspruch auf rechtliches Gehör, indem sie seine Beweisanträge abweise bzw. die Beweise nur unvollständig erhebe. Wie vorstehend dargelegt, stellt die Vorinstanz willkürfrei fest, es ergebe sich bereits aus den Aussagen des Beschwerdeführers, dass er in Kauf nahm, das Wohl seiner Kinder mit der Verbringung nach Nigeria massiv zu verletzen. Die Vorinstanz begründet zwar kurz, jedoch schlüssig, weshalb sie der Ansicht ist, die für den Entscheid notwendigen Beweise seien erhoben worden und zusätzliche Abklärungen würden ihre Überzeugung nicht beeinflussen (vgl. Urteil S. 17 f.; kantonale Akten, act. 330). Der Beschwerdeführer zeigt nicht auf, dass bzw. inwiefern die antizipierte Beweiswürdigung der Vorinstanz schlechterdings nicht mehr vertretbar sein soll. Es trifft zu, dass die Vorinstanz seinem Antrag auf Einholung der Akten betreffend seine Strafanzeige gegen die Kindsmutter wegen Widerhandlungen gegen das Betäubungsmittelgesetz vom 11. Mai 2010 grundsätzlich statt gab, die beigezogenen Strafakten jedoch unvollständig waren. Dies ist zwar bedauerlich, jedoch ist darin keine Verletzung seiner verfassungsmässigen Rechte zu sehen, da - wie die Vorinstanz zutreffend festhält - bei der zuständigen Staatsanwaltschaft keine weiteren Aktenstücke vorhanden waren (Urteil S. 18; kantonale Akten, act. 332). Kommt hinzu, dass der Beschwerdeführer nicht darlegt, inwiefern die in den Akten fehlenden Dokumente (polizeilicher Ermittlungsbericht und Protokoll seiner Einvernahme) geeignet wären, das vorinstanzliche Beweisergebnis zu beeinflussen, zumal sich deren Inhalt aus der Nichteintretensverfügung ergibt (vgl. kantonale Akten, act. 333/2). Ebenso wenig ist ersichtlich, inwiefern die Akten der Vormundschaftsbehörde Zürich bzw. der heutigen KESB und die Einvernahme von zwei Zeuginnen die Überzeugung der Vorinstanz sollten beeinflussen können. Wie der Beschwerdeführer selbst vorbringt, ist nicht relevant, ob die Kindsmutter mit Drogen handelte, sondern, ob der Beschwerdeführer hiervon ausging. Diesbezüglich ist jedoch in erster Linie sein Wissen bei der Verbringung der Kinder nach Nigeria im Oktober 2011 und nicht jenes im Jahr 2009 massgebend. Der Beschwerdeführer zeigt nicht auf, dass sich hierzu aus den von ihm beantragten Beweismitteln etwas entnehmen lässt.
2.4.4. Zusammengefasst ist die vorinstanzliche Sachverhaltsfeststellung und Beweiswürdigung nicht zu beanstanden. Die Vorinstanz durfte die Beweisanträge des Beschwerdeführers abweisen, ohne in Willkür zu verfallen. Sein rechtliches Gehör ist ebenso wenig verletzt wie der Grundsatz "in dubio pro reo". Da der Beschwerdeführer ernsthaft für möglich hielt, mit der Verbringung seiner Kinder nach Nigeria deren Interessen sowie Wohl massiv zu verletzen und er dies auch billigend in Kauf nahm, ist der vorinstanzliche Schluss, er habe hinsichtlich der Entführung eventualvorsätzlich gehandelt, bundesrechtskonform.
3.
3.1. Der Beschwerdeführer wendet sich gegen die Strafzumessung und beantragt, er sei mit einer Freiheitsstrafe von maximal dreieinhalb Jahren zu bestrafen. Er macht geltend, die Vorinstanz habe die nachteiligen Folgen der Entwicklung der Kinder, den Einfluss des neuen Umfelds sowie den Umfang der Einschränkung in ihrer Bewegungsfreiheit unzutreffend gewürdigt und deshalb die objektive Tatschwere zu hoch eingestuft. In subjektiver Hinsicht werfe sie ihm willkürlich ein egoistisches Verhalten vor und berücksichtige ungenügend bzw. gar nicht, dass er nicht direktvorsätzlich gehandelt sowie sich gemäss seinen heimatlichen Gesetzen und Traditionen im Recht gesehen habe. Schliesslich überschreite sie ihr Ermessen, indem sie seine Vorstrafen stärker gewichte als sein Geständnis zum äusseren Sachverhalt.
3.2. Das Bundesgericht hat die Grundsätze der Strafzumessung nach <ref-law> und die an sie gestellten Begründungsanforderungen wiederholt dargelegt (<ref-ruling> E. 5.4 ff. S. 59 ff. mit Hinweisen). Entsprechendes gilt für die Bildung der Einsatzstrafe und der Gesamtstrafe nach <ref-law> in Anwendung des Asperationsprinzips (<ref-ruling> E. 6.1.2 S. 67; <ref-ruling> E. 5.2 S. 122 f.; Urteil 6B_460/2010 vom 4. Februar 2011 E. 3.3.4, nicht publ. in: <ref-ruling>; je mit Hinweisen). Darauf kann verwiesen werden.
Es liegt im Ermessen des Sachgerichts, in welchem Umfang es die verschiedenen Strafzumessungsfaktoren berücksichtigt. Das Bundesgericht greift auf Beschwerde hin nur in die Strafzumessung ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen bzw. in Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet hat (<ref-ruling> E. 5.6 S. 61 mit Hinweis).
3.3.
3.3.1. Die Vorinstanz setzt die hypothetische Einsatzstrafe für die mehrfache qualifizierte Entführung auf fünfeinhalb Jahre fest und erhöht diese aufgrund des mehrfachen Entziehens von Minderjährigen um ein Jahr. In Berücksichtigung der Täterkomponenten erachtet sie insgesamt eine Freiheitsstrafe von sieben Jahren als angemessen (Urteil S. 19 ff.).
3.3.2. Hinsichtlich der objektiven Tatschwere der mehrfachen qualifizierten Entführung erwägt die Vorinstanz unter Hinweis auf ihre Ausführungen im aufgehobenen Urteil, der Beschwerdeführer habe die Ende 2011 erst dreieinhalb- resp. fünfjährigen Kinder an einem unbekannten Ort in Nigeria bei ihnen bisher nicht bekannten Personen und fernab der leiblichen Mutter belassen. Er habe keinen Kontakt zugelassen und eine Verabschiedung oder ein Lebenszeichen von der Mutter an ihre Kinder unterbunden. Die noch kleinen Kinder seien aus ihrer angestammten, vertrauten Umgebung vollkommen rücksichtslos herausgerissen und völlig entwurzelt worden. Erschwerend komme die auch innerhalb des qualifizierten Tatbestands als lang zu bezeichnende Deliktsdauer von eineinhalb Jahren hinzu. Zu Gunsten des Beschwerdeführers sei davon auszugehen, dass die Kinder nicht getrennt worden seien, sich am Ort ihres Aufenthalts grundsätzlich frei bewegen könnten, sie also nicht eingeschlossen seien, bei seinen Familienangehörigen oder Bekannten seien und es sich bei Nigeria um das Heimatland ihrer Eltern handle. Entgegen dem Einwand des Beschwerdeführers seien die mit der Rechtsgutverletzung unmittelbar einhergehenden Folgen bei der objektiven Tatschwere miteinzubeziehen. Sein Verschulden sei als erheblich zu bezeichnen und die hypothetische Einsatzstrafe auf fünfeinhalb Jahre festzusetzen (Urteil S. 20 ff.).
Nicht zu beanstanden ist, wenn die Vorinstanz beim objektiven Verschulden berücksichtigt, dass die Kinder die Mutter abrupt verloren sowie keinen Kontakt mehr zu ihr haben, und damit den nachteiligen Folgen für die Entwicklung der beiden Kinder Rechnung trägt. Dabei handelt es sich nicht um ein sachfremdes Kriterium, sondern um eine Folge der Entführung, welche bei der Strafzumessung beachtet werden darf (vgl. Urteil 6B_694/2012 vom 27. Juni 2013 E. 2.3.2). Inwiefern der vorinstanzliche Schluss, aufgrund der eigenen Äusserungen des Beschwerdeführers müsse davon ausgegangen werden, dass das neue Umfeld die Kindsmutter vor den Kindern schlecht mache (Urteil S. 21), willkürlich sein soll, zeigt dieser nicht substanziiert auf. Darauf ist nicht einzutreten. Keinen Bedenken begegnet auch, dass die Vorinstanz den Einwand der Verteidigung verwirft, es sei von einem geringen Eingriff in die Bewegungsfreiheit der Kinder auszugehen. Zwar trifft zu, dass die Fortbewegungsfreiheit der Kinder in Nigeria selbst nur minim eingeschränkt ist, da sie sich am Ort ihres Aufenthalts frei bewegen können. Jedoch fällt wie dargelegt wesentlich ins Gewicht, dass ihnen die Mutter genommen wurde und sie unabhängig vom Willen des Beschwerdeführers nicht zu dieser bzw. an ihren gewohnten Aufenthaltsort zurückzukehren können. Entgegen der Ansicht des Beschwerdeführers liegt kein "annähernd unbeachtlicher Eingriff in die Fortbewegungsfreiheit der Kinder" vor. Die von der Vorinstanz für das objektive Verschulden festgesetzte hypothetische Einsatzstrafe von fünfeinhalb Jahren erscheint zwar hoch, liegt jedoch angesichts der langen Deliktsdauer und des Umstands, dass es sich um zwei Kinder handelt, noch innerhalb ihres Ermessens.
3.3.3. Bezüglich der subjektiven Tatschwere wendet der Beschwerdeführer mit Hinweis auf seine Ausführungen zur Sachverhaltsfeststellung ein, die vorinstanzliche Annahme, er habe bloss aus Rache und Egoismus zum Nachteil seiner Kinder gehandelt, sei willkürlich. Da er sich damit vom verbindlich festgestellten Sachverhalt abwendet, ist darauf nicht einzutreten (vgl. E. 2; <ref-law>). Nicht zu beanstanden ist, dass die Vorinstanz das eventualvorsätzliche Handeln des Beschwerdeführers bloss in geringem Umfang verschuldensmindernd berücksichtigt. Wie sie zutreffend erwägt, hat er die Kinder direktvorsätzlich nach Nigeria verbracht, was unweigerlich mit einer massiven Beeinträchtigung ihres Wohls einherging (vgl. Urteil S. 24). Sein Einwand, es sei zu seinen Gunsten zu berücksichtigen, dass er die Kinder nicht zu fremden Personen, sondern zu ihren Grosseltern gebracht habe, geht an der Sache vorbei, da die Vorinstanz diesen Umstand bei der objektiven Tatschwere einbezieht (vgl. Urteil S. 21). Keinen Bedenken begegnet schliesslich, wenn die Vorinstanz das Vorbringen des Beschwerdeführers, er habe sich gemäss seinen heimatlichen Gesetzen und Traditionen im Recht gesehen, als unerheblich bezeichnet. Sie weist zu Recht darauf hin, dass der Beschwerdeführer seit 20 Jahren in der Schweiz lebt und mit der schweizerischen Rechtsordnung vertraut ist. Zudem hat er mehrfach die schweizerischen Behörden und schweizerisches Recht angerufen, womit er die schweizerische Zuständigkeit erkannte sowie anerkannte (Urteil S. 13, 24; aufgehobenes Urteil S. 12 zum Tatbestand des Entziehens von Minderjährigen). Insgesamt ist die Beurteilung der subjektiven Tatschwere als neutral nicht zu beanstanden.
3.3.4. Bei den Täterkomponenten wertet die Vorinstanz das Vorleben und die persönlichen Verhältnisse des Beschwerdeführers neutral. Eine erhöhte Strafempfindlichkeit verneint sie. Das Geständnis zum äusseren Sachverhalt wirke sich lediglich unwesentlich strafmindernd aus, da das Verfahren dadurch nicht wesentlich vereinfacht worden sei. Einsicht oder Reue in das Unrecht seiner Taten könne er keinesfalls strafmindernd für sich reklamieren. Das Beschleunigungsgebot sei nicht verletzt. Ferner weise der Beschwerdeführer eine nicht einschlägige Vorstrafe aus dem Jahr 2005 auf und habe während laufendem Strafverfahren sowie während der Probezeit delinquiert. Insgesamt würden die straferhöhenden die strafmindernden Umstände überwiegen, weshalb die Gesamtfreiheitsstrafe auf sieben Jahre festzusetzen sei (Urteil S. 24 f. mit Hinweis auf das aufgehobene Urteil S. 24 f. und das erstinstanzliche Urteil S. 52 f., 54).
Der Einwand des Beschwerdeführers, sein Geständnis zum äusseren Sachverhalt wirke sich wesentlich strafmindernd und die Vorstrafen unwesentlich straferhöhend aus, ist im Ergebnis verfehlt. Zutreffend ist sein Vorbringen, das mehrere Jahre zurück liegende SVG-Delikt wirke sich neutral oder kaum straferhöhend aus. Davon geht indessen auch die Vorinstanz aus (Urteil S. 24; aufgehobenes Urteil S. 25;erstinstanzliches Urteil S. 53). Der Beschwerdeführer wurde mit Urteil der Vorinstanz vom 8. Juni 2012 wegen Nötigung und mehrfacher Tätlichkeiten zu einer bedingten Geldstrafe von 40 Tagessätzen zu Fr. 10.-- und einer Busse verurteilt (vgl. E. 2.4.2 hiervor). Er wendet zu Recht ein, dass diese Vorstrafe nicht einschlägig ist und Bagatellcharakter hat, womit sie eher zu einer unwesentlichen Straferhöhung führen kann. Jedoch fällt diesbezüglich nicht unerheblich ins Gewicht, dass der Beschwerdeführer die vorliegend zu beurteilenden Taten während des hängigen Strafverfahrens wegen Nötigung und nach dessen Abschluss in der laufenden Probezeit beging. Fraglich erscheint jedoch, ob die eher geringen Vorstrafen zu einer Straferhöhung von mehr als sechs Monate führen dürfen. Die Frage kann jedoch offenbleiben. Jedenfalls würde eine bundesrechtswidrige Gewichtung der Vorstrafe nicht zur Aufhebung des angefochtenen Entscheids führen. Entgegen der Vorinstanz wirkt sich der Umstand, dass der Beschwerdeführer zugab, seine Kinder nach Nigeria verbracht zu haben, vorliegend nicht strafmindernd aus. Wie sie zutreffend erwägt, hat dies das Verfahren nicht entscheidend vereinfacht, da er nichts eingestand, was ihm nicht ohnehin hätte nachgewiesen werden können. Inwiefern sein Teilgeständnis das Verfahren vereinfacht haben soll, begründet auch der Beschwerdeführer nicht. Ferner hätte die Vorinstanz berücksichtigen dürfen, dass der Beschwerdeführer weder den konkreten Aufenthaltsort seiner Kinder bekannt gab noch die Rückführungsbemühungen unterstützte. Insgesamt hält sich der vorinstanzliche Schluss, die straferhöhenden Komponenten überwiegten die strafmindernden Umstände, innerhalb des sachrichterlichen Ermessens.
3.3.5. Die Freiheitsstrafe von sieben Jahren liegt auch bei einer Gesamtbetrachtung innerhalb des sachrichterlichen Ermessens und ist nicht zu beanstanden. Die Beschwerde ist in diesem Punkt abzuweisen.
4.
Seinen Antrag auf Genugtuung und Entschädigung begründet der Beschwerdeführer lediglich mit der Reduktion der Strafe bzw. gar nicht. Darauf ist nicht einzutreten, zumal es bei der Freiheitsstrafe von sieben Jahren bleibt.
5.
Der Beschwerdeführer kritisiert die Höhe der Genugtuung. Da ihm nur eventualvorsätzliches Handeln vorgeworfen werden könne, sei der Kindsmutter eine Genugtuung von Fr. 10'000.-- zuzusprechen.
Im aufgehobenen Urteil begründet die Vorinstanz schlüssig und nachvollziehbar, weshalb sie eine Genugtuungssumme von Fr. 30'000.-- als angemessen erachtet. So sei die Kindsmutter durch den abrupten sowie lange andauernden Entzug ihrer beiden Kinder und die damit verbundene Ungewissheit um deren Befinden in ihrer Psyche massiv tangiert, wobei das Verschulden des Beschwerdeführers als Verursacher dieses Zustands strafrechtlich erheblich wiege. Angesichts der völlig offenen Zukunft und des Umstands, dass die Kindsmutter keinerlei Kontakte zu ihren Kindern habe, erscheine der Betrag von Fr. 30'000.-- als angemessen (aufgehobenes Urteil S. 26 f.). Im angefochtenen Urteil erwägt die Vorinstanz zutreffend, dass die andere rechtliche Würdigung des Verhaltens des Beschwerdeführers die Höhe der Genugtuung nicht zu beeinflussen vermag (Urteil S. 26). Der Beschwerdeführer setzt sich mit den vorinstanzlichen Ausführungen nicht auseinander. Mit dem blossen Hinweis, er habe eventualvorsätzlich gehandelt, vermag er nicht aufzuzeigen, weshalb die Vorinstanz ihr Ermessen überschritten haben sollte. Unter Berücksichtigung der konkreten Verhältnisse verletzt die Vorinstanz dieses nicht, wenn sie (je Kind) eine Genugtuung von Fr. 15'000.-- als angemessen erachtet (vgl. hierzu Urteil 6B_694/2012 vom 27. Juni 2013 E. 3.3). Die Kritik an der Bemessung der Genugtuungssumme erweist sich damit als unbegründet, soweit sie überhaupt den Anforderungen von <ref-law> genügt.
6.
Der Beschwerdeführer rügt, die Vorinstanz hätte die Kosten der unentgeltlichen Vertretung der Kindsmutter definitiv auf die Gerichtskasse nehmen müssen. Er argumentiert, anders als <ref-law> enthalte <ref-law> keinen Verweis auf die Rückzahlungspflicht gemäss <ref-law>.
Die Rüge ist unbegründet. Das Bundesgericht hat bereits im Rückweisungsentscheid darauf hingewiesen, dass der Staat nach der Rechtsprechung die Kosten für die unentgeltliche Verbeiständung der Privatklägerschaft von der beschuldigten Person unter den gleichen Voraussetzungen zurückfordern kann, wie jene für die amtliche Verteidigung (vgl. Art. 426 Abs. 1 und 4, Art. 138 Abs. 1 und <ref-law>). Demnach wird die bedürftige beschuldigte Person grundsätzlich zur Kostentragung verurteilt, gleichzeitig wird jedoch im Urteil festgehalten, dass die Kosten für die amtliche Verteidigung und die unentgeltliche Verbeiständung der Privatklägerschaft unter Vorbehalt der Rückzahlungspflicht gemäss <ref-law> einstweilen auf die Gerichtskasse genommen werden (Urteil 6B_123/2014 vom 2. Dezember 2014 E. 6.3, nicht publ. in: <ref-ruling> mit Hinweis auf: Urteile 6B_150/2012 vom 14. Mai 2012 E. 2.1; 6B_112/2012 vom 5. Juli 2012 E. 1.2 f.; je mit Hinweisen).
7.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann.
Die Gerichtskosten sind dem Beschwerdeführer aufzuerlegen (<ref-law>). Sein Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist in Anwendung von <ref-law> abzuweisen, weil die Rechtsbegehren aussichtslos erschienen. Seiner finanziellen Lage ist bei der Bemessung der Gerichtskosten Rechnung zu tragen (<ref-law>). Der Beschwerdegegnerin 2 ist keine Entschädigung zuzusprechen, da ihr im bundesgerichtlichen Verfahren keine Umtriebe entstanden.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'600.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 14. April 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Andres