Sachverhalt:
A.
A.a. A.X._ (geb. 1965) ist Staatsangehöriger der Republik Côte d'Ivoire und reiste am 27. September 1999 in die Schweiz ein, wo er um Asyl ersuchte. Am 8. Februar 2000 heiratete er die Schweizer Bürgerin B.Y._ (geb. 1953) und erhielt in der Folge eine Aufenthaltsbewilligung für den Kanton Solothurn. Ab April 2001 lebte das Ehepaar getrennt. Am 14. Januar 2004 wurde die Verlängerung der Aufenthaltsbewilligung von A.X._ verweigert, weil die Ehegemeinschaft aufgegeben worden sei. Nachdem das Ehepaar X.Y._ das Eheleben wieder aufgenommen hatte, wurde diese Verfügung am 26. Januar 2004 in Wiedererwägung gezogen.
Am 28. November 2005 erteilte die Solothurner Ausländerbehörde A.X._ nach erneuter Untersuchung der Eheverhältnisse die Niederlassungsbewilligung. Zu diesem Zeitpunkt war der Behörde bekannt, dass A.X._ in seiner Heimat mit seiner Landsfrau C._ (geb. 1979) vier Kinder hatte, wovon eines während der Ehe mit B.Y._ am 20. Juli 2001 geboren wurde.
A.b. Am 1. August 2006 zog A.X._ in den Kanton Aargau, wo ihm die Erteilung einer Niederlassungsbewilligung verweigert wurde. Am 9. November 2006 teilte B.Y._ den Solothurner Behörden mit, dass sie sich von ihrem Mann getrennt habe. Am 6. September 2007 ging aus der Beziehung mit C._ mit Tochter D._ das fünfte Kind von A.X._ hervor.
A.c. Am 3. September 2008 stellte A.X._ ein Gesuch um Kantonswechsel in den Kanton Zürich. Dieses Gesuch wurde bewilligt und er erhielt eine Niederlassungsbewilligung mit Kontrollfrist bis zum 28. Februar 2013.
Die Ehe X.Y._ wurde am 19. Mai 2009 geschieden. Am 28. September 2010 verheiratete sich A.X._ mit C._ und beantragte am 23. Mai 2011 zunächst die Einreisebewilligung für seine Ehegattin und vier gemeinsame Kinder; später beschränkte er das Nachzugsgesuch auf seine Ehegattin und die Tochter D._.
B.
Das Migrationsamt des Kantons Zürich widerrief mit Verfügung vom 4. Oktober 2011 die Niederlassungsbewilligung von A.X._ und setzte ihm Frist zum Verlassen der Schweiz. Zudem wies es die Familiennachzugsgesuche für die Ehefrau und die Tochter D._ ab. Die hiergegen erhobenen Rechtsmittel an die Sicherheitsdirektion und das Verwaltungsgericht des Kantons Zürich blieben erfolglos.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 2. Mai 2013 beantragt A.X._, das angefochtene Urteil des Verwaltungsgerichts des Kantons Zürich vom 27. März 2013 sei aufzuheben und ihm die Niederlassungsbewilligung zu belassen. Eventualiter sei ihm die Jahresaufenthaltsbewilligung zu erteilen.
Das Verwaltungsgericht des Kantons Zürich und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Die Sicherheitsdirektion des Kantons Zürich verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Gegen den angefochtenen kantonal letztinstanzlichen Endentscheid über den Widerruf der Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht zulässig, weil grundsätzlich ein Anspruch auf das Fortbestehen dieser Bewilligung gegeben ist (vgl. Art. 83 lit. c Ziff. 2, Art. 86 Abs. 1 lit. d sowie Art. 90 BGG; <ref-ruling> E. 1.2.1 S. 4).
1.2. Mit der Beschwerde 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.).
1.3. Die Beschwerdeschrift hat gemäss <ref-law> die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzt (<ref-ruling> E. 2.1 S. 245 f.). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insoweit, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>). Eine diesen Anforderungen genügende Begründung ist hier nur teilweise zu erkennen. Soweit eine solche fehlt, kann auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht eingetreten werden.
2.
Der Beschwerdeführer beantragt vor dem Bundesgericht nur noch die Aufhebung des Widerrufs seiner Niederlassungsbewilligung, womit die Ablehnung des Familiennachzugsgesuchs für die Ehefrau sowie die Tochter nicht mehr Streitgegenstand im vorliegenden Verfahren bildet.
3.
3.1. Nach dem hier anwendbaren Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) kann die Niederlassungsbewilligung widerrufen werden, wenn der Ausländer oder sein Vertreter im Bewilligungsverfahren falsche Angaben macht oder wesentliche Tatsachen verschwiegen hat (Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. a AuG). Die unter dem alten Recht (Art. 9 Abs. 2 lit. a und Abs. 4 lit. a ANAG) zu diesem Widerrufsgrund entwickelte Praxis gilt im Wesentlichen auch für Art. 62 lit. a AuG. Namentlich muss die falsche Angabe oder das Verschweigen wesentlicher Tatsachen in der Absicht erfolgt sein, gestützt darauf den Aufenthalt oder die Niederlassung bewilligt zu erhalten. Der Ausländer ist verpflichtet, den Behörden wahrheitsgetreu über alles Auskunft zu geben, was für den Bewilligungsentscheid massgebend sein kann (Art. 3 Abs. 2 und Art. 13 f ANAG bzw. Art. 90 AuG). Wesentlich sind dabei nicht nur Umstände, nach denen die Fremdenpolizei ausdrücklich fragt, sondern auch solche, von denen der Gesuchsteller wissen muss, dass sie für den Bewilligungsentscheid massgeblich sein können (Urteile 2C_595/2011 vom 24. Januar 2012 E. 3.3; 2C_15/2011 vom 31. Mai 2011 E. 4.2.1). Als wesentlicher Umstand gilt gemäss ständiger Rechtsprechung insbesondere das Vorhandensein von vor- bzw. ausserehelichen Kindern bei Gesuchen zum Verbleib beim in der Schweiz ansässigen Ehepartner bzw. bei der Ehepartnerin (vgl. die Urteile 2C_243/2008 vom 18. Juni 2008 E. 2.3; 2A.423/2006 vom 26. Oktober 2006 E. 2.1; 2A.346/2004 vom 10. Dezember 2004 E. 2.2; je mit Hinweisen). Der Widerruf ist allerdings nur zulässig, wenn er aufgrund der relevanten Gesamtumstände verhältnismässig ist.
3.2. Die Vorinstanz hat festgestellt, dass der Beschwerdeführer bei seiner Einreise in die Schweiz 1999 seine damalige Lebensgefährtin und heutige Ehefrau sowie die drei gemeinsamen Kinder (geb. 1992, 1994 und 1997) in seinem Heimatland zurückliess. Nach der Heirat in der Schweiz gebar seine heutige Ehefrau - noch während der Ehe des Beschwerdeführers mit einer Schweizer Bürgerin - das vierte Kind. Von 2001 bis 2003 lebte das Ehepaar X.Y._ getrennt und 2006 erfolgte die definitive Trennung des Ehepaars. Am 6. September 2007 kam das fünfte Kind des Beschwerdeführers mit seiner heutigen Ehefrau zur Welt. Nach der Scheidung am 19. Mai 2009 heiratete der Beschwerdeführer am 28. September 2010 in seinem Heimatland die Mutter seiner fünf Kinder und beantragte am 23. Mai 2011 den Familiennachzug (vgl. angefochtener Entscheid E. 3.3).
3.3. Aufgrund dieser Umstände hat die Vorinstanz zu Recht gefolgert, dass der Beschwerdeführer den Kontakt zu seiner im Herkunftsland zurückgebliebenen Familie während der Ehe mit der Schweizer Bürgerin aufrechterhielt. Ebenso wenig zu beanstanden ist damit der Schluss der Vorinstanz, der Beschwerdeführer habe schon im Zeitpunkt der Erteilung der Niederlassungsbewilligung geplant, seine heutige Ehefrau dereinst zu heiraten und die Kinder in die Schweiz nachzuziehen.
3.4. Zwar ist einzuräumen, dass die Solothurner Behörden im Zeitpunkt der Erteilung der Niederlassungsbewilligung 2005 Kenntnis hatten von den ersten vier Kindern des Beschwerdeführers. Allerdings musste die Ausländerbehörde in Solothurn noch nicht davon ausgehen, dass der Beschwerdeführer dereinst seine Parallelfamilie in die Schweiz würde nachziehen wollen. Wie die Vorinstanz zu Recht ausführte, erfolgte diese Erkenntnis erst mit der Geburt des fünften Kindes 2007, der Heirat mit der Kindsmutter sowie dem Begehren um Familiennachzug (vgl. angefochtener Entscheid E 3.3). In diesem Zusammenhang ist auch zu erwähnen, dass die Ausländerbehörde des Kantons Solothurn in ihrer Verfügung vom 28. November 2005 explizit festgehalten hat, ein allfälliges Familiennachzugsgesuch für die im Heimatland lebende Familie würde zu einer Prüfung des Aufenthaltsrechts unter dem Aspekt des Rechtsmissbrauchs führen.
Die Solothurner Behörden haben somit - zu Gunsten des Beschwerdeführers - zunächst angenommen, die Beziehung zu seiner heutigen Ehefrau sei zwar problematisch, aber ein rechtsmissbräuchliches Verhalten liege (noch) nicht vor. Erst mit der Geburt eines weiteren Kindes 2007 bzw. mit dem Familiennachzugsgesuch mussten die Behörden schliesslich davon ausgehen, dass es sich um eine gleichzeitig gelebte Parallelbeziehung handelte.
3.5. Entgegen der Ansicht des Beschwerdeführers ist es derart offensichtlich, dass das Vorhandensein einer ausserehelichen Beziehung und von ausserehelichen Kindern im Heimatstaat bzw. der beabsichtige Familiennachzug in fremdenpolizeilicher Hinsicht von Relevanz ist, dass dies selbst einer gänzlich rechtsunkundigen Person ohne weiteres klar sein muss (vgl. Urteil 2C_72/2009 vom 5. März 2009 E. 3.2 mit Hinweisen). Der Beschwerdeführer kann daher das Bestehen einer Täuschungsabsicht nicht mit Erfolg bestreiten. Daran ändert auch nichts, dass das Migrationsamt angesichts der unübersichtlichen Familienverhältnisse im Allgemeinen und den in den Akten vorhandenen Hinweisen auf eine mögliche Parallelfamilie an sich gehalten gewesen wäre, vor Erteilung der Niederlassungsbewilligung noch vertiefter Abklärungen vorzunehmen (vgl. Urteil 2C_291/2012 vom 17. Januar 2013 E. 3.4).
Damit ist im Ergebnis der Widerrufsgrund von Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. a AuG erfüllt.
3.6. Der Widerruf der Niederlassungsbewilligung erweist sich, gestützt auf die Ausführungen der Vorinstanz (dortige E. 3.4 und 3.5), auch als verhältnismässig (vgl. Art. 96 AuG) : Der Beschwerdeführer ist erst im Alter von 34 Jahren in die Schweiz eingereist. Er ist in seinem Heimatland aufgewachsen und hat damit dort die prägenden Lebensjahre verbracht. Es darf davon ausgegangen werden, dass er mit den kulturellen und gesellschaftlichen Gepflogenheiten seines Heimatlandes nach wie vor vertraut ist. Trotz der mittlerweile 14-jährigen Anwesenheit in der Schweiz vermag der Beschwerdeführer keine besonders intensive, über eine normale Integration hinausgehende private Bindung zur oder in der Schweiz vorzuweisen. Hinzu kommt, dass seine Ehefrau und seine Kinder in der Republik Côte d'Ivoire leben, so dass sein Familienleben ohne weiteres dort geführt werden kann.
Was schliesslich die Sicherheitslage in der Republik Côte d'Ivoire betrifft, hat die Vorinstanz ausführlich dargelegt, warum der Vollzug der Wegweisung nicht unzumutbar im Sinne von Art. 83 Abs. 4 AuG ist. Soweit der Beschwerdeführer diese Ausführungen kritisiert und sinngemäss geltend macht, seine Wegweisung in die Republik Côte d'Ivoire sei im Sinne eines Vollzugshindernisses unzumutbar, ist auf seine Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht einzutreten (Art. 83 lit. c Ziff. 3 und 4 BGG). Seine entsprechenden Vorbringen können - mangels einer genügenden verfassungsrechtlichen Begründung - auch nicht im Rahmen einer subsidiären Verfassungsbeschwerde geprüft werden (vgl. Art. 117 i.V.m. 106 Abs. 2 BGG und <ref-ruling> E. 3.3 S. 310).
4.
Schliesslich beantragt der Beschwerdeführer eventualiter noch die Erteilung einer Aufenthaltsbewilligung im Sinne einer - im Vergleich zum Widerruf der Niederlassungsbewilligung - milderen Massnahme, ohne diesen Antrag substantiiert zu begründen. Nachdem der Beschwerdeführer jedoch den Widerrufsgrund nach Art. 62 lit. a AuG gesetzt hat und der Widerruf verhältnismässig ist, sind auch die Voraussetzungen zur Erteilung einer Aufenthaltsbewilligung nicht erfüllt (Urteil 2C_254/2010 vom 15. Juli 2010 E. 4.3). Der Eventualantrag ist somit ebenfalls abzuweisen.
5.
Die Beschwerde erweist sich demzufolge als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
Da dem Gesuch um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung vor Bundesgericht infolge Aussichtslosigkeit der Rechtsbegehren nicht entsprochen werden kann (<ref-law>), hat der unterliegende Beschwerdeführer grundsätzlich die bundesgerichtlichen Kosten zu tragen. Der finanziellen Lage des Beschwerdeführers wird indessen bei der Bemessung der Gerichtsgebühr Rechnung getragen. Es sind keine Parteientschädigungen geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt des Kantons Zürich, der Sicherheitsdirektion des Kantons Zürich, dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 7. Januar 2014
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger