Sachverhalt:
A.
A._ (geb. 1978) stammt aus Jamaika. Er reiste im April 2009 in die Schweiz ein. Am 11. Juni 2009 heiratete er eine Schweizerin, worauf ihm eine zuletzt bis am 10. Juni 2013 verlängerte Aufenthaltsbewilligung für den Kanton Zürich erteilt wurde. Die Ehegatten sind Eltern zweier im Juli 2011 bzw. Februar 2013 geborener Töchter, die Schweizer Bürger sind. Ein im April 2009 geborenes gemeinsames Kind verstarb im selben Jahr.
Bereits am 1. Juni 2012 verwarnte das Migrationsamt des Kantons Zürich A._ und stellte ihm schwerer wiegende ausländerrechtliche Massnahmen in Aussicht, falls er und die Familie weiterhin auf Sozialhilfe angewiesen sein sollten. Nachdem die Ehe am 5. Oktober 2012 aufgegeben worden war, genehmigte das Bezirksgericht Zürich die Eheschutzvereinbarung der Ehegatten am 19. Juli 2013. Darin wurde das Getrenntleben auf unbestimmte Zeit festgelegt. Die beiden Töchter wurden unter die Obhut der Mutter gestellt; die Kindsmutter und A._ verfügen über die gemeinsame elterliche Sorge. A._ verpflichtete sich sodann in der Eheschutzvereinbarung, die ihm zustehenden Kinderzulagen an die Kindsmutter weiterzuleiten.
B.
Das Migrationsamt wies am 13. Mai 2014 ein Gesuch A._s um Verlängerung der Aufenthaltsbewilligung ab und wies ihn an, die Schweiz zu verlassen. Einen hiergegen erhobenen Rekurs wies die Sicherheitsdirektion des Kantons Zürich ab. Die dagegen beim Verwaltungsgericht geführte Beschwerde blieb erfolglos (Urteil vom 29. April 2015).
C.
Mit Eingabe vom 10. Juni 2015 beantragt A._ dem Bundesgericht, das Urteil vom 29. April 2015 sei aufzuheben. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung.
Das Verwaltungsgericht und die Sicherheitsdirektion des Kantons Zürich verzichten darauf, sich vernehmen zu lassen. Das Staatssekretariat für Migration beantragt, die Beschwerde sei abzuweisen.
Mit Verfügung vom 11. Juni 2015 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.
Mit Schreiben vom 27. August 2015 informierte das Migrationsamt das Bundesgericht darüber, dass der Beschwerdeführer erneut von der Sozialhilfe abhängig sei und sich nunmehr um eine Teilzeitstelle bemühe. Mit Stellungnahme vom 27. April 2016 hält der Beschwerdeführer an seinen Anträgen fest.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist 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 (<ref-law>). Für das Eintreten genügt, wenn der Betroffene in vertretbarer Weise dartut, dass potenziell ein Anspruch auf die Bewilligung besteht; ob die jeweiligen Voraussetzungen tatsächlich gegeben sind, bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.1 S. 179 f., 497 E. 3.3 S. 500 f.). Der Beschwerdeführer macht in vertretbarer Weise einen Anspruch nach Art. Art. 50 Abs. 1 lit. a und b AuG sowie Art. 8 EMRK geltend, sodass die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist.
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 (Art. 97 Abs. 1 bzw. <ref-law>).
2.
2.1. Gemäss Art. 42 Abs. 1 AuG haben ausländische Ehegatten von Schweizerinnen und Schweizern, wenn sie mit diesen zusammenwohnen, Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung und - nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren - Anspruch auf Erteilung einer Niederlassungsbewilligung (Art. 42 Abs. 3 AuG). Nach Auflösung der Ehe- oder Familiengemeinschaft besteht der Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung weiter, wenn die Ehegemeinschaft mindestens drei Jahre bestanden hat und eine erfolgreiche Integration besteht (Art. 50 Abs. 1 lit. a AuG). Eine (relevante) Ehegemeinschaft liegt vor, solange die eheliche Beziehung tatsächlich gelebt wird und ein gegenseitiger Ehewille besteht. Dabei ist im Wesentlichen auf die Dauer der nach aussen wahrnehmbaren ehelichen Wohngemeinschaft abzustellen (vgl. <ref-ruling> E. 2 S. 231; <ref-ruling> E. 3.1.2 f. S. 347).
2.2. Die in Art. 50 Abs. 1 lit. a AuG vorausgesetzte Integration soll längerfristig und rechtmässig anwesenden Ausländerinnen und Ausländern ermöglichen, am wirtschaftlichen, sozialen und kulturellen Leben der Gesellschaft teilzuhaben (Art. 4 Abs. 2 AuG; vgl. <ref-ruling> E. 4.1 S. 4 f.). Dazu ist erforderlich, dass sich Ausländerinnen und Ausländer mit den gesellschaftlichen Verhältnissen und Lebensbedingungen in der Schweiz auseinandersetzen und eine Landessprache erlernen (Art. 2 Abs. 4 AuG). Nach Art. 77 Abs. 4 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit (VZAE, SR 142.201) liegt eine erfolgreiche Integration nach Art. 50 Abs. 1 lit. a AuG vor, wenn die Ausländerin oder der Ausländer namentlich die rechtsstaatliche Ordnung und die Werte der Bundesverfassung respektiert (lit. a) sowie den Willen zur Teilnahme am Wirtschaftsleben und zum Erwerb der am Wohnort gesprochenen Landessprache bekundet (lit. b, vgl. Urteile 2C_930/2012 vom 10. Januar 2013 E. 3.1, 2C_14/2014 vom 27. August 2014 E. 4.6.1). Nach Art. 4 der Verordnung vom 24. Oktober 2007 über die Integration von Ausländerinnen und Ausländern (VintA; SR 142.205) zeigt sich der Beitrag der Ausländerinnen und Ausländer zu ihrer Integration namentlich in der Respektierung der rechtsstaatlichen Ordnung und der Werte der Bundesverfassung (lit. a), im Erlernen der am Wohnort gesprochenen Landessprache (lit. b), in der Auseinandersetzung mit den Lebensbedingungen in der Schweiz (lit. c) sowie im Willen zur Teilnahme am Wirtschaftsleben und zum Erwerb von Bildung (lit. d). Das Bundesgericht hat festgehalten, dass das Adverb "namentlich", welches sowohl in <ref-law> wie auch in Art. 4 VintA verwendet wird, auf den nicht ausschliesslichen Charakter der in diesen Bestimmungen aufgezählten Kriterien hinweist. Bei der Prüfung der Integrationskriterien verfügen die zuständigen Behörden über einen grossen Ermessensspielraum, in welchen das Bundesgericht nur zurückhaltend eingreift (vgl. Art. 54 Abs. 2 und Art. 96 Abs. 1 AuG; vgl. Urteil 2C_668/2011 vom 23. Juli 2012 E. 3.2.1).
2.3. Bei einer ausländischen Person, die in der Schweiz beruflich integriert ist und eine feste Anstellung hat, die finanziell unabhängig ist, sich korrekt verhält und die örtliche Sprache beherrscht, bedarf es ernsthafter besonderer Umstände, um eine erfolgreiche Integration im Sinne von Art. 50 Abs. 1 lit. a AuG zu verneinen (Urteile 2C_749/2011 vom 20. Januar 2012 E. 3.3; 2C_839/2010 vom 25. Februar 2011 E. 7.1.2). Nicht erforderlich ist eine besonders qualifizierte berufliche Karriere (Urteil 2C_430/2011 vom 11. Oktober 2011 E. 4.2). Auch das Fehlen besonders enger sozialer Beziehungen schliesst für sich allein eine erfolgreiche Integration nicht aus (Urteil 2C_839/2010 vom 25. Februar 2011 E. 7.1.2), ebenso wenig das Fehlen von Vereinsmitgliedschaften (Urteil 2C_427/2011 vom 26. Oktober 2011 E. 5.3). Keine erfolgreiche Integration liegt vor, wenn eine Person kein Erwerbseinkommen erwirtschaften kann, welches ihren Konsum zu decken vermag, und sie während einer substanziellen Zeitdauer von Sozialleistungen abhängig war; jedenfalls wenn sich diese Situation nicht hinreichend verbessert (Urteile 2C_298/2014 vom 12. Dezember 2014 E. 6.3 und 6.4.2 in fine; 2C_930/2012 vom 10. Januar 2013 E. 3.1; 2C_857/2010 vom 22. August 2011 E. 2.3.1; 2C_546/2010 vom 30. November 2010 E. 5.2.3 f.). Geringfügige Strafen schliessen eine Integration nicht aus (Urteil 2C_749/2011 vom 20. Januar 2012 E. 4.3); ebensowenig, dass eine ausländische Person verschuldet ist, wenn sie im Begriff ist, die Schulden in wirksamer Weise zurückzubezahlen (vgl. Urteil 2C_352/2014 vom 18. März 2015 E. 4.5). Umgekehrt ergibt sich aus dem Umstand, dass die ausländische Person sich strafrechtlich nichts zuschulden hat kommen lassen und ihr Unterhalt ohne Sozialhilfe gewährleistet erscheint, für sich allein noch keine erfolgreiche Integration (Urteil 2C_830/2010 vom 10. Juni 2011 E. 2.2.2). Ein Indiz gegen eine solche ist der Umstand, dass das gesellschaftliche Leben einer ausländischen Person primär mit Angehörigen des eigenen Landes erfolgt (Urteile 2C_749/2011 vom 20. Januar 2012 E. 3.3; 2C_546/2010 vom 30. November 2010 E. 5.2.4). Kann sich der Betroffene auf einfache Weise in typischen alltäglichen Situationen verständigen und kurze Gespräche führen, hat er in sprachlicher Hinsicht jedoch als hinreichend integriert zu gelten (Urteil 2C_65/2014 vom 27. Januar 2015 E. 3.5).
3.
3.1. Vorliegend ist unbestritten, dass die Ehegemeinschaft des Beschwerdeführers seit der Heirat am 11. Juni 2009 bis zur Aufgabe der Gemeinschaft am 5. Oktober 2012 (Erlöschen des Ehewillens der Gattin) und somit mehr als drei Jahre in der Schweiz geführt wurde. Die Anforderungen an die Dauer des Zusammenlebens sind demnach erfüllt (vgl. hiervor E. 2.1 und <ref-ruling> E. 3.5.3 S. 295; <ref-ruling> E. 3.3 S. 117 ff.; <ref-ruling> E. 3.1.3 S. 347). Die Vorinstanz hat jedoch einen Anspruch nach Art. 50 Abs. 1 lit. a AuG auf Verlängerung der Aufenthaltsbewilligung mangels erfolgreicher Integration des Beschwerdeführers abgelehnt. Sie hat dies mit umfangreichen Sozialhilfebezügen während der gesamten Aufenthaltsdauer in der Schweiz begründet.
3.2. Gemäss den vorinstanzlichen Sachverhaltsfeststellungen musste der Beschwerdeführer sowohl während der Ehe als auch nach der Trennung der Ehegatten ununterbrochen von der Sozialhilfe unterstützt werden. Insgesamt wurden durch die Fürsorgebehörden zwischen der Heirat und Mitte Juli 2013 für den Beschwerdeführer und seine Familie Unterstützungsleistungen im Umfang von gegen Fr. 180'000.-- erbracht. Vom Auszug des Beschwerdeführers aus der gemeinsamen Wohnung bis Ende August 2014 hat er Sozialhilfeleistungen im Umfang von Fr. 25'000.-- beansprucht. Bis zum Zeitpunkt des vorinstanzlichen Urteils beliefen sich die Unterstützungsleistungen allein für den Beschwerdeführer auf insgesamt Fr. 130'000.--.
3.3. Der Beschwerdeführer rügt, das Integrationskriterium nach Art. 50 Abs. 1 lit. a AuG sei zukunftsgerichtet; massgebend für die Beurteilung einer erfolgreichen Integration sei, ob diese zum Zeitpunkt des vorinstanzlichen Urteils bejaht werden könne. Er macht geltend, er sei sozial und sprachlich gut integriert. Hinsichtlich der wirtschaftlichen Integration bringt der Beschwerdeführer vor, im Rahmen eines Arbeitsintegrationsprogramms habe er am 6. September 2010 eine Stelle mit einem Beschäftigungsgrad von 50% antreten können; später habe der Beschäftigungsgrad auf 80% ausgebaut werden können. Am 16. März 2015 sei ihm sodann der Einstieg in den ersten Arbeitsmarkt gelungen; seither finanziere er seinen Lebensunterhalt selbstständig.
3.3.1. Der Beschwerdeführer war während seines gesamten Aufenthalts in erheblichem Umfang von der Sozialhilfe abhängig. Obwohl sich seine Ehegattin vollzeitlich um die Kinder gekümmert hatte, war er nie im primären Arbeitsmarkt berufstätig. Es ist dem Beschwerdeführer zwar zugutezuhalten, dass er während vier Jahren in einem Arbeitsintegrationsprogramm teilzeitlich beschäftigt war, seine Arbeit zu voller Zufriedenheit erledigte und einen Teillohn erzielte. Die Integration in den sekundären Arbeitsmarkt hat indessen Sozialhilfecharakter; es geht darum, die beruflichen und sozialen Kompetenzen der betroffenen Personen durch staatliche Förderprogramme zu verbessern, ansonsten Leistungen gekürzt würden (vgl. dazu Urteil 2C_1092/2015 vom 13. April 2016 E. 2.3). Das Erwebseinkommen des Beschwerdeführers konnte demnach weder je seinen eigenen Unterhalt noch denjenigen seiner Familie decken. Der Beschwerdeführer konnte zum Zeitpunkt der Trennung von seiner Gattin nicht als integriert im Sinne von Art. 50 Abs. 1 lit. a AuG gelten (vgl. Urteile 2C_930/2012 vom 10. Januar 2013 E. 3; 2C_857/2010 vom 22. August 2011 E. 2.3.1; 2C_777/2013 vom 22. August 2010 E. 2.3.1).
3.3.2. Der Beschwerdeführer macht geltend, ihm sei die Loslösung von der Sozialhilfe jedenfalls am 16. März 2015 - rund eineinhalb Monate vor dem vorinstanzlichen Urteil - gelungen. Die Vorinstanz stellte zu jenem Zeitpunkt fest, dass ein Beschäftigungsgrad im Arbeitsvertrag vom 16. März 2015 nicht festgelegt wurde und sich der Umfang der Beschäftigung nach dem Bedarf des Arbeitgebers richtet. Es kann ihr zum damaligen Zeitpunkt keine Rechtsverletzung vorgeworfen werden, wenn sie eine Aussicht auf ein regelmässiges Einkommen verneinte (vgl. Urteil 2C_298/2014 vom 12. Dezember 2014 E. 6.4.2). Der Beschwerdeführer legt der vom 10. Juni 2015 datierten Beschwerde nunmehr eine Lohnabrechnung vom April 2015 bei. Das Migrationsamt lässt dem Bundesgericht am 27. August 2015 seinerseits die Information zukommen, der Beschwerdeführer werde bereits wieder von der Sozialhilfe unterstützt, wolle sich jedoch nunmehr um eine Teilzeitstelle bemühen. Beide vorgebrachten Sachverhaltselemente lassen indessen die diesbezüglichen vorinstanzlichen Feststellungen nicht offensichtlich unrichtig erscheinen (vgl. hiervor E. 1.2); auch können sie für das bundesgerichtliche Verfahren nicht entscheidwesentlich sein (<ref-law>). Die Vorinstanz durfte zum gegeben Zeitpunkt davon ausgehen, die berufliche Situation des Beschwerdeführers sei nicht stabilisiert. Auch aus dem Umstand, dass der Beschwerdeführer nicht straffällig wurde, ergibt sich noch keine erfolgreiche Integration im Sinne von Art. 50 Abs. 1 lit. a AuG (vgl. hiervor E. 2.3). Es kann vor diesem Hintergrund offenbleiben, ob eine Integration zum vom Beschwerdeführer behaupteten Zeitpunkt noch in hinreichendem Bezug zur Ehe stand und hätte berücksichtigt werden können (vgl. Urteil 2C_175/2015 vom 30. Oktober 2015 E. 3.2.3).
4.
Sind im Falle der Auflösung der ehelichen Gemeinschaft die Voraussetzungen von Art. 50 Abs. 1 lit. a AuG nicht gegeben, so bleibt gemäss Art. 50 Abs. 1 lit. b AuG zu prüfen, ob wichtige persönliche Gründe einen weiteren Aufenthalt in der Schweiz erforderlich machen, wie dies der Beschwerdeführer geltend macht.
4.1. Nach Art. 50 Abs. 1 lit. b und Abs. 2 AuG besteht der Bewilligungsanspruch nach einer gescheiterten Ehe bzw. Familiengemeinschaft fort, falls wichtige persönliche Gründe einen weiteren Aufenthalt in der Schweiz erforderlich machen (vgl. BGE <ref-ruling> E. 3.2 S. 348 ff.). Ein persönlicher, nachehelicher Härtefall setzt aufgrund der gesamten Umstände eine erhebliche Intensität der Konsequenzen für das Privat- und Familienleben voraus, die mit der Lebenssituation nach dem Dahinfallen der abgeleiteten Anwesenheitsberechtigung verbunden sein muss (vgl. <ref-ruling> E. 6 S. 403 f.; <ref-ruling> E. 3.2 S. 348 ff., je mit Hinweisen). Entscheidend ist, ob die persönliche, berufliche und familiäre Eingliederung der betroffenen ausländischen Person bei einer Rückkehr in ihre Heimat als stark gefährdet zu gelten hätte, hingegen nicht, ob ein Leben in der Schweiz einfacher wäre und - aus welchen Gründen auch immer - vorgezogen würde (vgl. BGE <ref-ruling> E. 3.2.3 S. 350). Bei der Beurteilung, ob ein wichtiger persönlicher Grund nach Art. 50 AuG vorliegt, können ausserdem die in <ref-law> erwähnten Gesichtspunkte im In- oder Heimatland eine Rolle spielen, auch wenn sie einzeln betrachtet grundsätzlich noch keinen Härtefall begründen, also der Grad der Integration, die Respektierung der Rechtsordnung, die Familienverhältnisse, die finanziellen Umstände, die Dauer der Anwesenheit oder der Gesundheitszustand des Betroffenen und seiner Familie (BGE <ref-ruling> E. 3.2.2 S. 349; vgl. auch das Urteil 2C_216/2009 vom 20. August 2009 E. 2.2).
4.2. Nach der Rechtsprechung kann der Fortbestand der elterlichen Beziehung zum hier gefestigt anwesenheitsberechtigten Kind einen wichtigen Grund zum Verbleib im Land bilden (Art. 50 Abs. 1 lit. b AuG; vgl. <ref-ruling> E. 3.4.1 S. 292; <ref-ruling> E. 3.1 S. 291). Dabei ist jeweils die Gesamtsituation zu würdigen und die entsprechende Regelung verfassungs- bzw. konventionskonform anzuwenden (<ref-law>; Art. 8 EMRK; Urteil 2C_1125/2014 vom 9. September 2015 E. 4.1). Der Anspruch aus Art. 50 Abs. 1 lit. b AuG geht in diesem Zusammenhang nicht weniger weit als jener aus <ref-law> bzw. Art. 8 EMRK (Urteile 2C_173/2011 vom 24. Juni 2011 E. 4; 2C_930/2012 vom 10. Januar 2013 E. 4.1; <ref-ruling> E. 2.2 in fine). Der nicht sorge- bzw. obhutsberechtigte ausländische Elternteil kann die familiäre Beziehung mit seinem Kind in der Regel nur in beschränktem Rahmen leben, nämlich durch die Ausübung des ihm eingeräumten Rechts auf persönlichen Umgang. Damit er dieses wahrnehmen kann, ist nicht unbedingt erforderlich, dass er sich dauerhaft im selben Land aufhält wie das Kind und dort über ein Anwesenheitsrecht verfügt. Unter dem Gesichtswinkel des Anspruchs auf Familienleben (<ref-law> sowie Art. 8 Ziff. 1 EMRK) kann es insbesondere bei deutlich überwiegendem öffentlichen Interesse (Straffälligkeit) genügen, wenn er den Kontakt im Rahmen von Kurzaufenthalten vom Ausland her ausüben kann, wobei allenfalls dessen Modalitäten anzupassen sind. Ein weitergehender Anspruch fällt indessen in Betracht, wenn in wirtschaftlicher und affektiver Hinsicht eine besonders enge Beziehung zum Kind besteht (so etwa bei einer geteilten Obhut bzw. einer faktisch gleichwertigen Betreuung mit gemeinsamem Sorgerecht), die Beziehung wegen der Distanz zum Heimatland des Ausländers praktisch nicht aufrecht erhalten werden kann und das bisherige Verhalten des Ausländers in der Schweiz zu keinen grösseren Klagen Anlass gegeben hat (<ref-ruling> E. 4.2 und 4.3 S. 149 ff.; <ref-ruling> E. 2.2 S. 319; <ref-ruling> E. 3c S. 5, 22 E. 4 S. 24 ff.; Urteile 2C_1231/2012 vom 20. Dezember 2012 E. 3.3; 2C_858/2012 vom 8. November 2012 E. 2.2; 2C_751/2012 vom 16. August 2012 E. 2.3). Auch die Prüfung der Situation eines Ausländers, der nicht mehr im gemeinsamen Haushalt mit seiner schweizerischen Ehegattin zusammenlebt, nicht über die Obhut verfügt, jedoch über das gemeinsame minderjährige Kind mit schweizerischer Nationalität noch die elterliche Sorge ausübt, orientiert sich an den dargelegten Abwägungskriterien eines besuchsberechtigten ausländischen Elternteils (<ref-ruling> E. 4.2 S. 149; Urteile 2C_1125/2014 vom 9. September 2015 E. 4.2 ff.; 2C_1095/ 2014 vom 17. Juli 2015 Sachverhalt lit. B und E. 4.3). Bei solchen Konstellationen stellt ein Verstoss gegen die öffentliche Ordnung keine unabhängige Bedingung dar, die zwangsläufig zum Widerruf der Aufenthaltsbewilligung führt (<ref-ruling> E. 3 und 4 S. 146 ff.). Es handelt sich aber immerhin um ein Kriterium unter anderen, das in der Interessenabwägung zu berücksichtigen ist. Dabei ist ihm grundsätzlich keine geringere Bedeutung einzuräumen, als dies im umgekehrten Familiennachzug für ein Kind mit Schweizer Bürgerrecht der Fall wäre (<ref-ruling> E. 4.1 S. 148 und E. 4.3 S. 150 f.). Massgeblich sind immer die tatsächlich gelebten Beziehungen der ausländischen Person zu den in der Schweiz aufenthaltsberechtigten Familienmitgliedern (<ref-ruling> E. 4.2 S. 149; <ref-ruling> E. 3.1 S. 148).
4.3. Der Beschwerdeführer macht geltend, er pflege zu seinen Kindern eine enge affektive Beziehung. Im Zeitpunkt des vorinstanzlichen Urteils sei er bei einer Cateringunternehmung angestellt gewesen und habe die ihm zustehenden Kinderzulagen wie vereinbart an die Kindsmutter weitergeleitet. Sodann stehe er in Verhandlung mit seiner Frau über eine Änderung der Eheschutzvereinbarung, was zu einer über die Kinderzulagen hinausgehenden finanziellen Unterstützung der Kinder führen werde. Die Trennung von seinen Kindern sei ihm nicht zumutbar.
4.4. Entgegen der Vorbringen ergibt sich aus der Situation des Beschwerdeführers kein Härtefall im Sinne von Art. 50 Abs. 1 lit. b AuG:
4.4.1. Nach den vorinstanzlichen Sachverhaltsfeststellungen besucht der Beschwerdeführer seine Kinder regelmässig; nach seinen eigenen Vorbringen sieht er sie mehrmals pro Woche und telefoniert täglich mit ihnen. Er verfügt damit zweifellos über eine enge affektive Beziehung im Sinne der eingangs erwähnten Rechtsprechung, wie dies die Vorinstanz zu Recht erwog (<ref-ruling> E. 3.2 S. 147; <ref-ruling> E. 2.3 ff. S. 319 ff.; <ref-ruling> E. 3c S. 5). Wenn das Verwaltungsgericht demgegenüber davon ausgeht, der Beschwerdeführer unterhalte zu seinen Kindern keine enge wirtschaftliche Beziehung, so ist dies nicht zu beanstanden: Der Beschwerdeführer bezahlt nach wie vor keine Unterhaltsbeiträge für seine Kinder. Er kümmert sich zwar mittels Betreuungsaufgaben ebenfalls um sie und hat gewisse Naturalleistungen erbracht. Spezifische Hinweise indessen, wonach diese einen Umfang erreicht hätten, dass seine Ehegattin einer regelmässigen Arbeit hätte nachgehen können, ergeben sich zum Zeitpunkt des vorinstanzlichen Urteils nicht (vgl. Urteil 2C_1125/2014 vom 9. September 2015 E. 4.6.1). Die Kindsmutter umsorgt denn auch vollumfänglich die Kinder (vgl. hiervor E. 3.3.1). Trotz umfassender Sozialleistungen konnte sich der Beschwerdeführer sodann nie im primären Arbeitsmarkt etablieren. Die Vorinstanz hat über eine lange Zeit keine ernsthaften Bemühungen zur Verbesserung der Einkommenssituation beim Beschwerdeführer feststellen können. Namentlich ergeben sich keine Hinweise, dass der Beschwerdeführer über die lange Zeit unverschuldet arbeitslos blieb und deswegen Unterhaltsbeiträge für seine Kinder nicht leisten konnte (vgl. Urteil 2C_1141/2014 vom 10. September 2015 E. 3.3.3). Durch den umfangreichen Sozialhilfebezug besteht einerseits ein qualifizierter Verstoss gegen die öffentliche Ordnung (<ref-ruling> E. 3 und 4 S. 146 ff. mit Verweis auf <ref-ruling> E. 2.2.4 S. 158). Andererseits fehlt es an einer engen wirtschaftlichen Beziehung des Beschwerdeführers zu seinen Kindern im Sinne der Rechtsprechung zu Art. 8 EMRK, die als Beitrag für das Wohl des Kindes vom nicht obhutsberechtigten ausländischen Elternteil vorausgesetzt wird.
4.4.2. Ein Härtefall im Sinne von Art. 50 Abs. 1 lit. b AuG ergibt sich schliesslich nicht aus der Rückkehr in das Heimatland des Beschwerdeführers. Er hat den grössten Teil seines Lebens in seinem Herkunftsland verbracht und ist mit den dortigen sozio-kulturellen Gegebenheiten bestens vertraut. Eine Rückkehr trifft den Beschwerdeführer und seine Töchter angesichts der Erschwerung der Vater-Kind-Beziehungen und der Beeinträchtigung des Familienlebens hart. Der Beschwerdeführer hat sich umgekehrt lange und auch in jüngster Zeit nicht hinreichend bemüht, Unterhaltsbeiträge für die Kinder zu entrichten und sich von der erheblichen staatlichen Unterstützung zu lösen. Auch eine ausländerrechtliche Verwarnung am 1. Juni 2012 liess den Beschwerdeführer nicht die Notwendigkeit erkennen, seine finanzielle Situation grundlegend zu ändern. Angesichts der lange andauernden, umfangreichen und als wesentlich selbstverschuldet zu wertenden Sozialhilfeabhängigkeit vermag das private Interesse das öffentliche Interesse an der Beendigung des Aufenthalts nicht zu überwiegen.
5.
Nach dem Gesagten ist die Beschwerde abzuweisen. Dem Verfahrensausgang entsprechend wird der Beschwerdeführer kostenpflichtig. Er ersucht indessen um unentgeltliche Prozessführung und Verbeiständung. Da die Beschwerde nicht zum vornherein aussichtslos war und der Beschwerdeführer bedürftig ist, kann die beantragte unentgeltliche Rechtspflege bewilligt und auf die Erhebung von Gerichtskosten verzichtet werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
2.1. Es werden keine Kosten erhoben.
2.2. Dem Beschwerdeführer wird Rechtsanwalt Marc Spescha, Zürich, als Rechtsbeistand beigegeben. Ihm wird aus der Gerichtskasse eine Entschädigung von Fr. 2'000.-- ausgerichtet.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 12. Mai 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Zünd
Die Gerichtsschreiberin: Hänni