Sachverhalt:
A.
A.a. X._ wurde am 8. Mai 1978 als Staatsangehöriger von Kuba geboren. Am 19. September 2003 heiratete er in Kuba die xxx geborene Schweizerin Y._. Nach seiner Einreise in die Schweiz am 25. Februar 2004 wurde ihm die Aufenthaltsbewilligung zum Verbleib bei der Ehefrau erteilt; er reiste jedoch vor der Zustellung der Bewilligung, im März 2004, wieder nach Kuba aus. Am 27. Dezember 2005 kehrte er in die Schweiz zurück und erhielt abermals eine Aufenthaltsbewilligung, welche letztmals bis am 10. August 2010 verlängert wurde.
A.b. Am xxx wurde die gemeinsame Tochter A._ geboren. Nach einem (ersten) Vorfall von häuslicher Gewalt, welcher am 22. Mai 2008 zu einer Verurteilung führen sollte, trennte sich Y._ am 22. Dezember 2006 von ihrem Mann. Sie lebte zunächst im L._, danach bei ihren Eltern. Mit Urteil des Gerichtspräsidiums M._ vom 17. Januar 2007 wurde vom Getrenntleben der Eheleute seit dem 22. Dezember 2006 Vormerk genommen und A._ unter die Obhut der Mutter gestellt. X._ erhielt die Erlaubnis, seine Tochter an zwei Wochenenden pro Monat im Beisein einer Drittperson zu besuchen. Ferner wurde für A._ eine Beistandschaft zur Organisation und Überwachung des Besuchsrechts errichtet.
Am xxx brachte Y._ die Zwillinge B._ und C._ zur Welt, deren Vater X._ ist. Für diese Kinder wurde ebenfalls eine Beistandschaft angeordnet.
A.c. Seit xxx unterhielt X._ mit der in P._ wohnhaften italienischen Staatsangehörigen Z._ eine unstete Beziehung, welche durch längere Trennungen unterbrochen wurde. Am xxx kam der gemeinsame Sohn E._ zur Welt.
Y._ gebar am xxx den Sohn D._, dessen Vater ebenfalls X._ ist. Dieser lebte ab Februar 2011 mit Z._ zusammen, bevor die Stadtpolizei P._ am 12. August 2011 seine Wegweisung aus deren Wohnung für 14 Tage und für diesen Zeitraum ein Rayon- und Kontaktverbot anordnete. Im November 2011 zogen X._ und Z._ erneut zusammen.
A.d. Auf gemeinsamen Antrag von X._ und Y._ hob die Vormundschaftsbehörde der Stadt P._ am 20. Oktober 2011 die Beistandschaft für A._ - und mit weiteren Beschlüssen angeblich auch für die übrigen gemeinsamen Kinder - auf.
Zwischen 1. Mai 2007 und 31. Januar 2011 wurde X._ durch die Sozialen Dienste der Stadt P._ mit Fr. 71'176.45 unterstützt.
A.e. Strafrechtlich trat X._ zunächst folgendermassen in Erscheinung:
- Urteil des Bezirksgerichts P._ vom 22. Mai 2008: Geldstrafe von 130 Tagessätzen (bedingt vollziehbar mit einer Probezeit von drei Jahren) zu Fr. 40.-- und Busse von Fr. 1'000.-- wegen einfacher Körperverletzung, Drohung, mehrfacher Tätlichkeiten und Sachbeschädigung im Wesentlichen zum Nachteil seiner Ehefrau;
- Urteil des Obergerichts des Kantons Zürich (nachfolgend: Obergericht) vom 31. Oktober 2011: 22 Monate Freiheitsstrafe (im Umfang von elf Monaten bedingt aufgeschoben mit einer Probezeit von drei Jahren) wegen mehrfacher unbefugter Datenbeschaffung, mehrfachen (teilweise versuchten) Betrugs, mehrfacher Urkundenfälschung und unrechtmässiger Aneignung; Verlängerung der Probezeit für die am 22. Mai 2008 ausgefällte bedingte Geldstrafe um ein Jahr.
B.
B.a. Am 24. Februar 2012 wies das Migrationsamt des Kantons Zürich (nachfolgend: Migrationsamt) das Gesuch um Verlängerung der Aufenthaltsbewilligung von X._ ab und wies ihn auf den Zeitpunkt der Entlassung aus dem Strafvollzug aus der Schweiz weg.
B.b. Im März 2012 erhob Y._ infolge häuslicher Gewalt zwei Mal Anzeige gegen X._, verzichtete jedoch darauf, Strafantrag zu stellen. Nach Aussage von Y._ habe X._ sie genötigt, ein positiv lautendes Schreiben zuhanden des Migrationsamts aufzusetzen, und ihr gedroht, sie umzubringen, falls er ausgewiesen werde.
Mit Strafbefehl vom 28. März 2012 verurteilte die Staatsanwaltschaft IV des Kantons Zürich X._ wegen Fälschung von Ausweisen zu einer bedingt vollziehbaren Freiheitsstrafe von 14 Tagen (Probezeit drei Jahre) als Zusatzstrafe zum Urteil des Obergerichts vom 31. Oktober 2011.
Im August 2012 wurde gegen X._ zudem ein Strafverfahren wegen Drohung und Körperverletzung gegenüber einem Arbeitskollegen eröffnet.
Ab dem 5. November 2012 befand sich X._ im Strafvollzug.
B.c. Den gegen die Verfügung des Migrationsamts vom 24. Februar 2012 erhobenen Rekurs wies die Sicherheitsdirektion des Kantons Zürich (nachfolgend: Sicherheitsdirektion) am 30. November 2012 ab. Das Verwaltungsgericht des Kantons Zürich (nachfolgend: Verwaltungsgericht) bestätigte diesen Entscheid auf Beschwerde hin mit Urteil vom 26. Juni 2013.
C.
C.a. X._ erhebt am 27. August 2013 Beschwerde an das Bundesgericht mit den Anträgen, das angefochtene Urteil in allen Punkten, auch bezüglich der verweigerten unentgeltlichen Rechtspflege, aufzuheben und ihm die Aufenthaltsbewilligung zu verlängern. In verfahrensrechtlicher Hinsicht beantragt er die Gewährung der unentgeltlichen Prozessführung unter Beiordnung seines Rechtsvertreters.
C.b. Das Verwaltungsgericht verzichtet ausdrücklich auf Vernehmlassung, ebenso die Sicherheitsdirektion. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde. X._ lässt sich mit Replik vom 20. Januar 2014 vernehmen.
C.c. Mit Präsidialverfügung vom 12. September 2013 ist der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt worden.

Erwägungen:
1.
1.1. Der verfahrensabschliessende Entscheid des Verwaltungsgerichts als letzter kantonaler Gerichtsinstanz in einer Angelegenheit des öffentlichen Rechts unterliegt grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>, <ref-law>, <ref-law>). Gemäss <ref-law> ist die Beschwerde unzulässig gegen Entscheide auf dem Gebiet des Ausländerrechts betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
1.1.1. Der Beschwerdeführer ist Vater von fünf in der Schweiz lebenden Kindern, von denen vier über das Schweizer Bürgerrecht und eines über die Niederlassungsbewilligung verfügen und zu denen der Beschwerdeführer - in unterschiedlicher Häufigkeit - Kontakt pflegt. Aufgrund des gefestigten Anwesenheitsrechts der Kinder kann sich der Beschwerdeführer auf Art. 8 Ziff. 1 EMRK berufen (vgl. <ref-ruling> E. 1.3.1 S. 145). Ob das in dieser Bestimmung garantierte Recht auf Achtung des Familienlebens verletzt ist, bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.1 S. 179).
1.1.2. Der Beschwerdeführer kann sich zudem auf Art. 50 AuG berufen. Zwar hatte er die Ehegemeinschaft mit Y._ bereits Ende 2006 aufgegeben. Er verfügte jedoch im Zeitpunkt des Inkrafttretens des AuG am 1. Januar 2008 noch bis zum 10. August 2008 über eine Aufenthaltsbewilligung, welche auf der Ehe beruhte (zum altrechtlichen Anspruch auf Bewilligungsverlängerung kraft formellen Bestands der Ehe vgl. Urteil 2C_613/2013 vom 1. Februar 2014 E. 1.1). Ob der Anspruch zu bejahen ist, bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.1 S. 179).
1.2. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist zulässig.
1.3. Die übrigen Sachurteilsvoraussetzungen sind offensichtlich erfüllt; auf die Beschwerde ist einzutreten. Für die hilfsweise erhobene subsidiäre Verfassungsbeschwerde bleibt gemäss <ref-law> kein Raum, weshalb darauf nicht einzutreten ist.
2.
2.1. 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>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (<ref-ruling> E. 1.4.1 S. 254). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 2.5 S. 314).
2.2. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinn von <ref-law> beruht (<ref-law>). Die beschwerdeführende Partei kann die Feststellung des Sachverhalts unter den gleichen Voraussetzungen beanstanden, wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Eine entsprechende Rüge ist rechtsgenüglich substanziiert vorzubringen (<ref-ruling> E. 2.5 S. 314).
2.3. Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Unzulässig sind hingegen neue Tatsachen, die bereits der Vorinstanz hätten vorgelegt werden können (<ref-ruling> E. 4.4.3 S. 129). In seiner Replik reicht der Beschwerdeführer diverse Unterlagen ein, welche - soweit überhaupt rechtserheblich - schon der Vorinstanz hätten vorgelegt werden können. Es ist nicht ersichtlich, inwiefern diese Beweismittel unter <ref-law> fallen könnten, weshalb sie im vorliegenden Verfahren unbeachtet bleiben.
Tatsachen oder Beweismittel, welche sich auf das vorinstanzliche Prozessthema beziehen, sich jedoch erst nach dem angefochtenen Entscheid ereignet haben oder entstanden sind, können von vornherein nicht durch das angefochtene Urteil veranlasst worden sein (vgl. Urteil 2C_833/2011 vom 6. Juni 2012 E. 1.2 mit Hinweis). Die nach dem 26. Juni 2013 datierenden Schriftstücke sind als so genannte "echte Noven" im bundesgerichtlichen Verfahren in jedem Fall unzulässig (<ref-ruling> E. 2.1 S. 344).
3.
Der Beschwerdeführer macht geltend, Art. 3 Abs. 6 Anhang I FZA (SR 0.142.112.681) sei verletzt worden.
3.1. Gemäss Art. 3 Abs. 6 Anhang I FZA dürfen die Kinder eines Staatsangehörigen einer Vertragspartei ungeachtet dessen, ob dieser im Hoheitsgebiet der anderen Vertragspartei eine Erwerbstätigkeit ausübt oder keine Erwerbstätigkeit ausübt oder eine Erwerbstätigkeit ausgeübt hat, unter den gleichen Bedingungen wie die Staatsangehörigen des Aufnahmestaates, sofern sie in dessen Hoheitsgebiet wohnen, am allgemeinen Unterricht sowie an der Lehrlings- und Berufsausbildung teilnehmen. Die Bestimmung ist Art. 12 der Verordnung Nr. 1612/68 des Rates vom 15. Oktober 1968 über die Freizügigkeit der Arbeitnehmer innerhalb der Gemeinschaft (ABl. L 257 vom 19. Oktober 1968 S. 2 ff.) nachgebildet (<ref-ruling> E. 3.1 S. 396).
3.2. Der Gerichtshof der Europäischen Gemeinschaften (EuGH) hat in Auslegung von Art. 3 Abs. 6 Anhang I FZA Folgendes entschieden: Die Kinder eines EU-Bürgers, die sich in einem Mitgliedstaat niedergelassen haben, während der Elternteil dort ein Aufenthaltsrecht als Wanderarbeitnehmer hatte, dürfen sich weiter in diesem Mitgliedstaat aufhalten, um am allgemeinen Unterricht gemäss Art. 12 der Verordnung Nr. 1612/68 teilnehmen zu können. Dabei ist nicht von Belang, ob die Eltern der Kinder inzwischen geschieden wurden, ob nur der eine Elternteil EU-Bürger, jedoch nicht mehr Wanderarbeitnehmer im Aufnahmestaat ist oder ob die Kinder selbst nicht über die EU-Bürgerschaft verfügen (Urteil des EuGH vom 17. September 2002 C-413/99 Baumbast, Slg. 2002 I-7091 Randnr. 63). Sofern die Kinder ein entsprechendes Aufenthaltsrecht geltend machen können, erlaubt Art. 12 der Verordnung Nr. 1612/68 dem die Sorge tatsächlich ausübenden Elternteil unabhängig von dessen Staatsangehörigkeit, sich bei diesen aufzuhalten, damit sie ihr Recht auf Bildung wahrnehmen können (Urteil Baumbast, Randnr. 75).
Das Urteil Baumbast wurde in der Folge bestätigt und dahingehend präzisiert, dass dem Elternteil, der die Sorge für die Kinder tatsächlich wahrnimmt, ein Anspruch auf Aufenthalt in Anwendung von Art. 12 der Verordnung Nr. 1612/68 zukommt, ungeachtet dessen, ob er über ausreichende Existenzmittel zur Vermeidung der Sozialhilfeabhängigkeit und über eine Krankenversicherung im Aufnahmestaat verfügt (Urteile des EuGH vom 23. Februar 2010 C-310/08 Ibrahim, Randnr. 25 ff., und C-480/08 Teixeira, Randnr. 34 ff.; vgl. zum Ganzen FERDINAND WOLLENSCHLÄGER, Aktuelle Fragen der EU-Personenfreizügigkeit, in: Achermann et al. [Hrsg.], Jahrbuch für Migrationsrecht 2009/2010, S. 23 ff.).
3.3. Was die Anwendung des FZA betrifft, wird gemäss Art. 16 Abs. 2 FZA die einschlägige Rechtsprechung des Gerichtshofs der Europäischen Gemeinschaften vor dem Zeitpunkt der Unterzeichnung berücksichtigt, soweit hierfür Begriffe des Gemeinschaftsrechts herangezogen werden; über die Rechtsprechung nach dem Zeitpunkt der Unterzeichnung wird die Schweiz unterrichtet. Das FZA wurde am 21. Juni 1999 abgeschlossen, so dass für das Bundesgericht die Rechtsprechung des EuGH bis zu diesem Zeitpunkt massgebend ist. Um eine möglichst parallele Rechtslage zu gewährleisten, weicht das Bundesgericht praxisgemäss nicht ohne triftigen Grund von der nach diesem Zeitpunkt ergangenen Rechtsprechung des EuGH ab (<ref-ruling> E. 4.1.1 S. 397; <ref-ruling> E. 3.1 S. 70).
Die zitierten Urteile des EuGH Baumbast, Ibrahim und Teixeira sind nach dem 21. Juni 1999 ergangen. Das Bundesgericht hat die Frage, ob diese Rechtsprechung zu übernehmen sei, in <ref-ruling> E. 4.2.1 nicht abschliessend entschieden. Dies ist auch im vorliegenden Fall nicht notwendig, da der Beschwerdeführer aus dieser Rechtsprechung nichts für sich ableiten kann.
3.4. Der Zweck des in Art. 3 Abs. 6 des Anhangs I zum FZA übernommenen selbständigen Anwesenheitsrechts für Kinder von Bürgern aus EU- oder EFTA-Staaten bzw. deren Partnern liegt darin, die Integration im Aufnahmestaat durch die Teilnahme am allgemeinen Unterricht zu fördern (vgl. Urteil Baumbast, Randnr. 59). Dies setzt voraus, dass die Kinder bei (noch) intakter Familiengemeinschaft tatsächlich begonnen haben, sich durch die Teilnahme am Unterricht in die Gesellschaft des Aufnahmestaates zu integrieren. Bei Kleinkindern, die noch in erster Linie auf den familiären Bereich bezogen leben, ist dies nicht der Fall, auch wenn sie in eine Tageskrippe oder allenfalls in den Kindergarten gehen (<ref-ruling> E. 4.2.2 S. 399). Der Sohn E._, von dessen Anwesenheitsrecht der Beschwerdeführer ein eigenes Aufenthaltsrecht ableiten will, war im Zeitpunkt des angefochtenen Urteils xxx Jahre alt. Bei dieser Sachlage ist Art. 3 Abs. 6 Anhang I FZA von vornherein nicht einschlägig.
Es ist überdies fraglich, ob die angerufene Rechtsprechung auch dann gilt, wenn das Kind - wie hier - die Ausbildung im Aufnahmestaat ohnehin absolvieren kann, weil der andere Elternteil (hier die Mutter) Staatsangehöriger der EU ist, ebenfalls im Aufnahmestaat wohnt und das Sorgerecht hat. In dieser Konstellation bedarf es des zusätzlichen Aufenthalts des Vaters nicht, um dem Kind die Teilnahme am Unterricht zu ermöglichen; der Zweck von Art. 3 Abs. 6 Anhang I FZA würde durch die Verweigerung des Aufenthaltsrechts des Vaters nicht vereitelt.
Die Frage braucht aber nicht vertieft zu werden. Selbst wenn E._ unter Art. 3 Abs. 6 Anhang I FZA fallen würde, könnte der Beschwerdeführer daraus kein Aufenthaltsrecht für sich selbst ableiten, da er die elterliche Sorge für E._ nicht ausübt. Die Vorinstanz hat willkürfrei und für das Bundesgericht verbindlich festgestellt, dass Z._ das Sorgerecht für E._ allein innehat (vgl. <ref-law>) und dem Beschwerdeführer lediglich ein Recht auf angemessenen persönlichen Verkehr gemäss <ref-law> zukommt. Entgegen dem Vorbringen des Beschwerdeführers spielt es keine Rolle, dass er und die Kindsmutter "im Zeitpunkt der Verhaftung" zusammenlebten. Ein gefestigtes Konkubinat mit Z._ lag ganz bestimmt nicht vor und ein gemeinsames Sorgerecht (welches hätte beantragt werden müssen, vgl. <ref-law>) stand nie zur Debatte. Eine allfällige Berufung auf die zitierte Rechtsprechung des EuGH würde somit auch daran scheitern, dass diese die (tatsächlich ausgeübte) elterliche Sorge der rechtsuchenden Person ausdrücklich voraussetzt.
4.
Der Beschwerdeführer rügt eine Verletzung von Art. 8 EMRK sowie von Art. 3 des Übereinkommens vom 20. November 1989 über die Rechte des Kindes (SR 0.107, nachfolgend: UNO-Kinderrechtekonvention).
4.1. Vor seiner Verhaftung habe er ein Jahr mit E._ zusammengelebt; das Verhältnis mit Z._ habe sich stabilisiert. Sie würden ein eheähnliches Leben führen, wodurch ein Besuchsrecht obsolet werde. Z._ und das Kind würden ihn regelmässig im Strafvollzug besuchen, was zeige, dass die Beziehung zu seinem Sohn gelebt und intensiv sei.
4.2. Die Vorinstanz hat zu Recht hervorgehoben, dass der nicht sorge- bzw. obhutsberechtigte ausländische Elternteil den Kontakt zu seinem Kind von vornherein nur in beschränktem Rahmen pflegen kann, nämlich durch die Ausübung des ihm eingeräumten Besuchsrechts. Um dieses wahrnehmen zu können, ist in der Regel keine dauernde Anwesenheit im Gastland erforderlich. Unter dem Gesichtspunkt des Anspruchs auf Familienleben nach Art. 8 Ziff. 1 EMRK ist es grundsätzlich ausreichend, wenn das Besuchsrecht im Rahmen von Kurzaufenthalten vom Ausland her ausgeübt werden kann, wobei allenfalls die Modalitäten des Besuchsrechts entsprechend auszugestalten sind. Gemäss der ständigen Rechtsprechung des Bundesgerichts kann ein weitergehender Anspruch nur in Betracht fallen, wenn in wirtschaftlicher und affektiver Hinsicht eine besonders enge Beziehung zum Kind besteht, diese Beziehung wegen der Distanz zum Herkunftsland der ausländischen Person praktisch nicht aufrechterhalten werden könnte und deren bisheriges Verhalten in der Schweiz zu keinerlei Klagen Anlass gegeben hat (sog. "tadelloses Verhalten"; vgl. <ref-ruling> E. 3c S. 5; <ref-ruling> E. 4 S. 24 ff.; Urteile 2C_586/2013 vom 3. Dezember 2013 E. 3.2.6; 2C_329/2013 vom 27. November 2013 E. 3.2).
Die erwähnte Rechtsprechung wurde in erster Linie für geschiedene Ehepartner entwickelt, welche vom sorgeberechtigten Elternteil getrennt leben. Sie ist aber gleichermassen anwendbar auf den unverheirateten, nicht sorgeberechtigten Elternteil. Denn rechtlich betrachtet hat auch dieser nur Anspruch auf angemessenen persönlichen Verkehr mit dem Kind, selbst wenn die Partner zusammenleben. Diese Konstellation dürfte ohnehin selten sein, da ein unverheiratetes Paar, welches mit einem gemeinsamen Kind zusammenlebt, in der Regel das gemeinsame Sorgerecht gemäss <ref-law> beantragen wird.
4.3. Nach den verbindlichen Feststellungen der Vorinstanz hat der Beschwerdeführer E._ nach dessen Geburt nicht sogleich anerkannt. Erst ein Jahr danach hatten er und Z._ wieder vermehrt Kontakt, und der Beschwerdeführer lebte von Februar 2011 bis Mitte August bei ihr. In dieser Zeit kam es zu häuslicher Gewalt; zudem gab Z._ gegenüber den Behörden an, der Beschwerdeführer habe sich zu wenig um E._ gekümmert. Von November 2011 bis Anfang November 2012 lebten der Beschwerdeführer und Z._ erneut zusammen, wobei sich der Kontakt zu E._ regelmässiger gestaltete. Das Zusammenleben des Beschwerdeführers mit seinem Sohn E._ dauerte höchstens eineinhalb Jahre und wurde mit dem Strafantritt Anfang November 2012 beendet; nach eigenen Aussagen besuchte Z._ den Beschwerdeführer mit dem Kind zwei Mal im Strafvollzug.
4.4. Es kann offen bleiben, ob in Bezug auf E._ eine besonders enge affektive Beziehung gemäss der neuen bundesgerichtlichen Praxis zur Intensität des Besuchsrechts (vgl. Urteil 2C_1112/2012 vom 14. Juni 2013 E. 2, zur Publikation vorgesehen) zu bejahen wäre. Da der Beschwerdeführer weder seine Unterhaltspflichten erfüllt noch ein tadelloses Verhalten im Sinn der zitierten Rechtsprechung (vgl. E. 4.2) an den Tag gelegt, sondern sogar einen Widerrufsgrund im Sinn von Art. 62 lit. b AuG gesetzt hatte (vgl. E. 5.1), ist ein Anspruch aus Art. 8 Ziff. 1 EMRK jedenfalls zu verneinen.
Im Übrigen ist darauf hinzuweisen, dass die UNO-Kinderrechtekonvention keine weitergehenden Ansprüche auf Bewilligung vermittelt als die EMRK (Urteile 2C_236/2013 vom 19. August 2013 E. 5.3.2; 2C_339/2013 vom 18. Juli 2013 E. 2.9 mit Hinweisen).
4.5. Auch aus dem Urteil des EGMR Udeh gegen Schweiz vom 16. April 2013 (Nr. 12020/09, in: Plädoyer 2013 3 S. 64) kann der Beschwerdeführer nichts zu seinen Gunsten ableiten. Abgesehen davon, dass sich die familiäre Situation in jenem Fall anders präsentierte, kann das erwähnte Urteil des EGMR nicht als Grundsatzurteil gelten. Dieses erscheint vielmehr als spezifischer Anwendungsfall der bisherigen Praxis des EGMR (vgl. insb. das Urteil Üner gegen Niederlande vom 18. Oktober 2006, Recueil CourEDH 2006-XII S. 159 §§ 54 ff.; vgl. auch die Urteile Boultif gegen Schweiz vom 2. August 2001 [Nr. 54273/00]; Emre gegen Schweiz vom 11. Oktober 2011 [Nr. 5056/10]), die von der Vorinstanz korrekt angewendet worden ist (vgl. Urteile 2C_522/2013 vom 23. Dezember 2013 E. 4.7; 2C_586/2013 vom 3. Dezember 2013 E. 3.2.5; 2C_360/2013 vom 21. Oktober 2013 E. 2.5; 2C_339/2013 vom 18. Juli 2013 E. 2.9; 2C_139/2013 vom 11. Juni 2013 E. 7.5). Zudem hat das Bundesgericht die Bedeutung des Urteils Udeh stark relativiert, im Wesentlichen mit der Begründung, der EGMR habe im erwähnten Entscheid diverse Umstände berücksichtigt, die erst nach der Beurteilung durch das Bundesgericht eingetreten sind (Urteil 2C_365/2013 vom 30. August 2013 E. 2.4, zur Publikation vorgesehen).
5.
Der Beschwerdeführer macht ferner eine Verletzung von Art. 50 Abs. 1 AuG in Verbindung mit Art. 96 AuG sowie von <ref-law> geltend.
5.1. Gemäss Art. 50 Abs. 1 AuG besteht nach Auflösung der Ehe- oder der Familiengemeinschaft der Anspruch des Ehegatten auf Erteilung und Verlängerung der Aufenthaltsbewilligung nach den Art. 42 und 43 AuG weiter, wenn die Ehegemeinschaft mindestens drei Jahre bestanden hat und eine erfolgreiche Integration besteht (lit. a) oder wenn wichtige persönliche Gründe einen weiteren Aufenthalt in der Schweiz erforderlich machen (lit. b).
Der Beschwerdeführer war seit dem 19. September 2003 mit Y._ verheiratet. Für die Dreijahresfrist nach Art. 50 Abs. 1 lit. a AuG zählen jedoch nur die in der Schweiz verbrachten Ehejahre (<ref-ruling> E. 3.3). Die Frist hat somit am 27. Dezember 2005 zu laufen begonnen. Die Ehegemeinschaft wurde bereits am 22. Dezember 2006 aufgehoben; die Dreijahresfrist ist klar nicht erfüllt. Zudem fehlt es offensichtlich am Erfordernis der erfolgreichen Integration, so dass ein Anspruch gestützt auf Art. 50 Abs. 1 lit. a AuG zu verneinen ist.
Der Beschwerdeführer macht keinen nachehelichen Härtefall im Sinn von Art. 50 Abs. 1 lit. b AuG geltend. Unter diesem Titel könnte die Verhältnismässigkeit der Trennung von den ehelichen Kindern unter den in E. 4.2 genannten Kriterien geprüft werden; der Beschwerdeführer gibt jedoch an, dass er diese vier Kinder seit der Einleitung des Scheidungsverfahrens nicht mehr sehe, weil Y._ sie ihm vorenthalte. Wie es sich damit verhält, braucht nicht abschliessend geprüft zu werden: Mit der Tochter A._ hat der Beschwerdeführer nur sehr kurze Zeit, während knapp elf Monaten, zusammengelebt. Mit den Kindern B._, C._ und D._ hat der Beschwerdeführer nie zusammengelebt. Wie den Akten zu entnehmen ist, gestaltete sich das Besuchsrecht nicht reibungslos, so dass ein Anspruch auf umgekehrten Familiennachzug auch hinsichtlich der gemeinsamen Kinder mit Y._ zu verneinen wäre. Dies gilt umso mehr, als der Beschwerdeführer durch die Verurteilung zu einer Freiheitsstrafe von 22 Monaten unzweifelhaft einen Widerrufsgrund gemäss Art. 62 lit. b AuG gesetzt hat (vgl. <ref-ruling> E. 4.2 S. 379), wodurch der Anspruch nach Art. 50 AuG zum Erlöschen gebracht wird (Art. 51 Abs. 2 lit. b AuG).
5.2. Der Beschwerdeführer erachtet die Nichtverlängerung der Aufenthaltsbewilligung als unverhältnismässig und beruft sich auf Art. 96 Abs. 1 AuG. Die Verhältnismässigkeitsprüfung nach Art. 8 Ziff. 2 EMRK ist in der in E. 4.2 zitierten Rechtsprechung enthalten, wonach ein Anspruch des nicht sorgeberechtigten Elternteils auf Verbleib in der Schweiz nur unter besonderen Voraussetzungen bejaht werden kann. Das Nämliche gilt unter dem Gesichtspunkt von Art. 50 Abs. 1 lit. b AuG.
Es mag angefügt werden, dass der Beschwerdeführer als Erwachsener in die Schweiz gekommen ist und im Zeitpunkt des angefochtenen Urteils siebeneinhalb Jahre hier gelebt hat. Er konnte beruflich nur mit grosser Mühe Fuss fassen und musste jahrelang von der Sozialhilfe unterstützt werden. Die Rückkehr nach Kuba ist dem noch jungen Beschwerdeführer ohne weiteres zumutbar, zumal er während der letzten Jahre mehrere Reisen dorthin unternommen hat und nicht nur seine Familie, sondern auch ein weiteres Kind von ihm dort lebt.
5.3. Die Vorinstanz erwog im Zusammenhang mit den strafrechtlichen Verurteilungen des Beschwerdeführers, weder die Beziehung zu seiner Frau, zu den Kindern noch zu seiner Freundin hätten ihn von weiterem Delinquieren abgehalten, würden doch auch aktuell Strafverfahren gegen ihn laufen. Der Beschwerdeführer sieht darin, dass ein laufendes Strafverfahren bei der Legalprognose berücksichtigt worden sei, einen Verstoss gegen die Unschuldsvermutung gemäss <ref-law>.
<ref-law> schützt die konkret angeklagte Person im jeweiligen Verfahren vor Vorverurteilung, der Missachtung des Grundsatzes "in dubio pro reo" und vor Ersatzverurteilung mittels Kostenauflage ( HANS VEST, in: Ehrenzeller et al. [Hrsg.], Die schweizerische Bundesverfassung, Kommentar, 2. Aufl. 2008, N. 5 zu <ref-law>, Hervorhebung im Original). Nach bundesgerichtlicher Rechtsprechung kann die Unschuldsvermutung aber auch ausserhalb eines Strafverfahrens Wirkungen haben: Staatliche Behörden dürfen bei Fehlen einer rechtskräftigen Verurteilung niemanden als schuldig behandeln oder bezeichnen ( ESTHER TOPHINKE, Das Grundrecht der Unschuldsvermutung, 1999, S. 157). Demgemäss wäre es nicht zulässig, in einem laufenden Strafverfahren einen Rückfall zu erblicken. Dies tat aber die Vorinstanz nicht, wenngleich ihre Formulierung etwas unglücklich gewählt ist. Sie erwog, es könne - auch aufgrund der laufenden Strafverfahren - nicht ausgeschlossen werden, dass der Beschwerdeführer erneut rückfällig werde. Eine solche Aussage ist mit <ref-law> vereinbar, denn auch ohne laufendes Strafverfahren konnte ein Rückfall nicht ausgeschlossen werden. So bezeichnete bereits das Obergericht in seinem Urteil vom 31. Oktober 2011 die Legalprognose des Beschwerdeführers als "recht getrübt". Dem Beschwerdeführer ist darin zuzustimmen, dass seine Legalprognose durch das laufende Strafverfahren nicht verändert worden ist. Dies ändert aber nichts daran, dass ihm das Obergericht eine erhebliche Rückfallgefahr attestiert hat; darauf durfte die Vorinstanz abstellen.
6.
Schliesslich moniert der Beschwerdeführer, die Vorinstanz habe <ref-law> verletzt, indem sie ihm die unentgeltliche Rechtspflege verweigert habe.
In Anbetracht der Verfehlungen des Beschwerdeführers, namentlich der Vorfälle von häuslicher Gewalt und der Verurteilung zu 22 Monaten Freiheitsstrafe, hat die Vorinstanz das Begehren des Beschwerdeführers, auch im Licht der Rechtsprechung in vergleichbaren Fällen, zu Recht als aussichtslos bezeichnet. Eine Verletzung von <ref-law> liegt nicht vor.
7.
Nach dem Gesagten ist die Beschwerde als unbegründet abzuweisen.
7.1. Mit Blick auf das ausführlich begründete Urteil der Vorinstanz muss die Beschwerde an das Bundesgericht ebenfalls als aussichtslos gelten. Das Gesuch um unentgeltliche Rechtspflege ist daher abzuweisen; der finanziellen Situation des Beschwerdeführers kann bei der Kostenauflage gemäss <ref-law> Rechnung getragen werden.
7.2. Ausgangsgemäss ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2.
Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
4.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
5.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 23. Februar 2014
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Genner