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. 