Sachverhalt:
A.
B._ wurde 2013 als Tochter von A._ und C._ geboren. Die nicht miteinander verheirateten Eltern trennten sich an Weihnachten 2014. B._ zog mit ihrer Mutter vom damaligen gemeinsamen Wohnsitz der Eltern in U._ nach V._. Der Vater blieb in U._.
Im Februar 2015 wurde bei der Kindes- und Erwachsenenschutzbehörde (KESB) V._ ein Verfahren betreffend elterliche Sorge, Zuteilung der Obhut und Regelung des persönlichen Verkehrs bzw. der Betreuungsanteile anhängig gemacht. Mit Beschluss der KESB V._ vom 6. September 2016 wurde B._ unter die gemeinsame elterliche Sorge beider Eltern gestellt. Die Obhut wurde der Mutter zugeteilt und es wurde die Vereinbarung der Eltern vom 22./25. Juli 2016 betreffend die Betreuung ihrer Tochter genehmigt. Diese Vereinbarung sieht vor, dass der Vater die Tochter alle vier Wochen von Donnerstagabend bis Sonntagabend betreut, zuzüglich Ferienbesuchsrecht.
B.
Bereits am 19. Mai 2016 und damit vor dem Entscheid der KESB hatte B._, vertreten durch ihre Mutter, beim Bezirksgericht V._ gegen den Vater auf Unterhalt geklagt. Dieses verurteilte den Vater mit Entscheid vom 22. Dezember 2016 dazu, ihr vom 1. Januar 2017 bis zum 31. Juli 2017 monatlich Fr. 530.-- und vom 1. August 2017 bis zum ordentlichen Abschluss einer angemessenen Ausbildung (auch über die Volljährigkeit hinaus) monatlich Fr. 580.-- an Barunterhalt zu bezahlen, wobei es diese Beiträge indexierte. Weitergehende Klagebegehren wies es ab.
Auf Berufung des Vaters, mit welcher er in erster Linie ein Nichteintreten auf die Klage beantragte und in zweiter Linie deren Abweisung, bestätigte das Obergericht des Kantons Zürich mit Urteil vom 31. Januar 2018 im Wesentlichen den erstinstanzlichen Entscheid, wobei es allerdings die Unterhaltspflicht erst ab Juni 2017 laufen liess und die Indexklausel dem gestiegenen Stand der Lebenshaltungskosten anpasste.
C.
A._ (Beschwerdeführer) gelangt mit Beschwerde in Zivilsachen vom 14. März 2018 an das Bundesgericht. Er verlangt, den angefochtenen Entscheid aufzuheben und in erster Linie auf die Klage nicht einzutreten. Eventualiter sei die Klage abzuweisen und subeventualiter zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Sodann beantragt er die Gewährung der aufschiebenden Wirkung und der unentgeltlichen Rechtspflege.
Mit Verfügung vom 15. März 2018 wies der Präsident der urteilenden Abteilung das Gesuch um aufschiebende Wirkung ab.
B._ (Beschwerdegegnerin) beantragt mit Eingabe vom 1. April 2019 die Abweisung der Beschwerde, soweit darauf einzutreten sei. Darauf replizierte der Beschwerdeführer am 15. April 2019; die Beschwerdegegnerin duplizierte am 29. April 2019. Die Vorinstanz verzichtete auf eine Vernehmlassung. Das Bundesgericht hat die kantonalen Akten beigezogen.

Erwägungen:
1.
1.1. Angefochten ist der Endentscheid (<ref-law>) einer letzten kantonalen Instanz, die als oberes Gericht auf Rechtsmittel hin entschieden hat (<ref-law>). Der Streit dreht sich um den Unterhalt eines minderjährigen Kindes, mithin eine Zivilsache (<ref-law>) vermögensrechtlicher Natur. Die gesetzliche Streitwertgrenze von Fr. 30'000.-- (Art. 74 Abs. 1 Bst. b BGG) ist erreicht (Art. 51 Abs. 1 Bst. a und Abs. 4 BGG). Die Beschwerde wurde rechtzeitig eingereicht (<ref-law>). Sie ist unter Vorbehalt der nachfolgenden Ausführungen grundsätzlich zulässig.
1.2. Mit der Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 f. BGG geltend gemacht werden. Das Bundesgericht wendet das Recht in diesem Bereich von Amtes wegen an (<ref-law>) und prüft mit freier Kognition, ob der angefochtene Entscheid Recht verletzt. Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen, und es kann sie mit einer Begründung abweisen, die von der Argumentation der Vorinstanz abweicht (<ref-ruling> E. 2.4 mit Hinweisen). Das Bundesgericht befasst sich aber nur mit formell ausreichend begründeten Einwänden (<ref-law>; <ref-ruling> E. 1.2.2). Auf rein appellatorische Kritik tritt es nicht ein (<ref-ruling> E. 2.4 mit Hinweis). Sodann ist es an den festgestellten Sachverhalt grundsätzlich gebunden (<ref-law>). Wird eine offensichtlich unrichtige, d.h. willkürliche Sachverhaltsfeststellung gerügt, so gilt hierfür - ebenso wie für die behauptete Verletzung von verfassungsmässigen Rechten - das strenge Rügeprinzip (Art. 97 Abs. 1 i.V.m. <ref-law>; dazu im Einzelnen: <ref-ruling> E. 2.3 mit Hinweisen). Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Diesen Anforderungen genügt die Beschwerdeschrift nicht, soweit der Beschwerdeführer darin auf Ausführungen in seinen im kantonalen Verfahren gemachten Eingaben verweist (<ref-ruling> E. 2 mit Hinweis). Auch beanstandet er die Höhe einzelner Bedarfspositionen (namentlich betreffend Krankenkasse, Mietanteil und Fremdbetreuungskosten der Tochter) als Verletzung von <ref-law>, obwohl es sich hier um Tatfragen handelt (Urteil 5A_435/2011 vom 14. November 2011 E. 9.2, in: FamPra.ch 2012 S. 192). Willkür in der Sachverhaltsfeststellung wirft der Beschwerdeführer der Vorinstanz diesbezüglich nicht vor. Auf die Beschwerde ist demnach in diesem Umfang nicht einzutreten. Ebenfalls unberücksichtigt bleiben die von der Beschwerdegegnerin in ihrer Vernehmlassung vorgetragenen echten Noven (<ref-ruling> E. 3.1.2 mit Hinweis), namentlich betreffend die Zahl der im Jahr 2018 stattgefundenen Besuche.
2.
2.1. In erster Linie macht der Beschwerdeführer geltend, die Klage sei nicht gültig eingeleitet worden. Die Kindsmutter hätte die Rechtsvertreterin der Beschwerdegegnerin nicht mandatieren dürfen, da ihr die Entscheidungsbefugnis hierfür als gemeinsam Sorgeberechtigte nicht allein zustehe (<ref-law>). Ohnehin sei ihre Vertretungsmacht wegen Interessenkollision von Gesetzes wegen entfallen (<ref-law>).
2.2. Die Eltern leiten gemäss <ref-law> im Blick auf das Wohl des Kindes seine Pflege und Erziehung und treffen unter Vorbehalt seiner eigenen Handlungsfähigkeit die nötigen Entscheidungen (Abs. 1). Der Elternteil, der das Kind betreut, kann allein entscheiden, wenn die Angelegenheit alltäglich oder dringlich ist (Abs. 1bis Ziff. 1) oder der andere Elternteil nicht mit vernünftigem Aufwand zu erreichen ist (Abs. 1bis Ziff. 2).
Laut <ref-law> haben die Eltern von Gesetzes wegen die Vertretung des Kindes gegenüber Drittpersonen im Umfang der ihnen zustehenden elterlichen Sorge (Abs. 1). Sind beide Eltern sorgeberechtigt, so dürfen gutgläubige Drittpersonen voraussetzen, dass jeder Elternteil im Einvernehmen mit dem andern handelte (Abs. 2). <ref-law> bestimmt für den Fall, dass die Eltern am Handeln verhindert sind oder in einer Angelegenheit Interessen haben, die denen des Kindes widersprechen, dass die Kindesschutzbehörde einen Beistand ernennt oder diese Angelegenheit selber regelt (Abs. 2). Bei Interessenkollision entfallen von Gesetzes wegen die Befugnisse der Eltern in der entsprechenden Angelegenheit (Abs. 3). Die Kindesschutzbehörde kann dem Beistand besondere Befugnisse übertragen, namentlich die Vertretung des Kindes bei der Wahrung seines Unterhaltsanspruches (Art. 308Abs. 2 ZGB).
Nach <ref-law> ordnet das Gericht wenn nötig die Vertretung des Kindes an und bezeichnet als Beiständin oder Beistand eine in fürsorgerischen und rechtlichen Fragen erfahrene Person (Abs. 1). Es prüft die Anordnung der Vertretung insbesondere, wenn die Eltern unterschiedliche Anträge bezüglich des Unterhaltsbeitrages stellen (Abs. 2 Bst. a Ziff. 5). Diese Bestimmung war bis zum 31. Dezember 2016 nur auf eherechtliche Verfahren anwendbar (AS 2010 1809), gilt seit dem 1. Januar 2017 nun aber auch für selbständige Unterhaltsklagen (AS 2015 4304-4306; <ref-law>).
2.3. Im Zeitpunkt der Einleitung der Unterhaltsklage (19. Mai 2016) war die Kindsmutter Alleininhaberin der elterlichen Sorge. In Anwendung von <ref-law> konnte sie somit die Rechtsvertreterin der Beschwerdegegnerin mit der Einleitung der Unterhaltsklage gültig beauftragen (zur Problematik des Interessenkonflikts vgl. hinten E. 2.7). Der diesbezügliche Vorwurf, auf die Klage hätte nicht eingetreten werden dürfen, erweist sich als unbegründet.
2.4. Seit dem 6. September 2016 haben der Beschwerdeführer und die Kindsmutter die elterliche Sorge gemeinsam inne. Es stellt sich die Frage, ob für den weiteren Verlauf des Unterhaltsprozesses für die Beschwerdegegnerin ein Beistand hätte ernannt werden müssen. Die Alleinentscheidungsbefugnis der obhutsberechtigten Mutter nach <ref-law> fällt ausser Betracht, da das Führen eines Unterhaltsprozesses keine alltägliche oder dringliche Angelegenheit darstellt (AFFOLTER-FRINGELI/VOGEL, Berner Kommentar, 2016, N. 36a zu <ref-law>; BRÄNDLI, Kinderunterhalt: Interessenkollisionen bei der Vertretung, Plädoyer 2019 S. 38; GEISER, Übersicht über die Revision des Kindesunterhaltsrechts, AJP 2016 S. 1289; MARANTA/ FASSBIND, Interessenkollisionen im Kindesunterhaltsrecht?, ZKE 2016 S. 460).
2.5. Die Vorinstanz erwog, ein Interessenkonflikt sei nicht ersichtlich, denn es liege sowohl im Interesse der Beschwerdegegnerin als auch ihrer Mutter, dass sich der Beschwerdeführer am Kindesunterhalt beteilige. Umgekehrt verliere der Beschwerdeführer seine Verwaltungskompetenz insoweit, als sein eigener Unterhaltsbeitrag für die nicht unter seiner Obhut stehende Tochter betroffen sei. Gemeinsame elterliche Sorge bedeute nicht, dass die Eltern bei der Verwaltung des Kindesvermögens stets gemeinsam handeln müssten.
2.6. Die Lehre ist sich mit Bezug auf die Zulässigkeit einer Vertretung des Kindes durch den obhutsberechtigten Elternteil uneinig (bejahend: AFFOLTER-FRINGELI/VOGEL, a.a.O., N. 36a zu <ref-law>; FOUNTOULAKIS/BREITSCHMID, in: Basler Kommentar, Zivilgesetzbuch, 6. Aufl. 2018, N. 7 zu <ref-law>; MARANTA/FASSBIND, a.a.O., S. 459 ff.; ROELLI, in: Handkommentar zum Schweizer Privatrecht, 2. Aufl. 2012, N. 2 zu <ref-law>; SENN, Verfahrensrechtliche Streiflichter zu den Revisionen der elterlichen Sorge und des Kindesunterhaltsrechts, FamPra.ch 2017 S. 982; ZOGG, Selbständige Unterhaltsklagen mit Annexentscheid über die weiteren Kinderbelange - verfahrensrechtliche Fragen, FamPra.ch 2019 S. 16; verneinend: BRÄNDLI, a.a.O., S. 41; GEISER, a.a.O., S. 1288 f.; KONFERENZ FÜR KINDES- UND ERWACHSENENSCHUTZ, Praxisanleitung Kindesschutzrecht, 2017, Rz. 14.51; SCHWEIGHAUSER/STOLL, Neues Kindesunterhaltsrecht - Bilanz nach einem Jahr, FamPra.ch 2018 S. 649).
2.7. Nach der im Wesentlichen unbestritten gebliebenen Rechtsprechung ist grundsätzlich abstrakt zu bestimmen, ob eine Interessenkollision im Sinn von Art. 306 Abs. 2 und 3 ZGB vorliegt oder nicht. Von einer solchen ist die Rechtsprechung ausgegangen, wenn sich die Interessen des Vertretenen und des gesetzlichen Vertreters widersprechen (<ref-ruling> E. 4c) oder wenn sich der gesetzliche Vertreter von Interessen ihm nahestehender Dritter, die nicht mit jenen des Vertretenen übereinstimmen, beeinflussen lassen könnte (<ref-ruling> E. 4). Entscheidend ist die Frage, ob die Möglichkeit besteht, dass der gesetzliche Vertreter zum Nachteil des Vertretenen handelt (vgl. AFFOLTER-FRINGELI/VOGEL, a.a.O., N. 36 zu <ref-law>; s.a. schon SCHNYDER/MURER, Berner Kommentar, 1984, N. 83 zu <ref-law>).
2.7.1. Offensichtlich ist die Interessenkollision zwischen dem Kind und dem auf Unterhalt eingeklagten Elternteil (AFFOLTER-FRINGELI/VOGEL, a.a.O., N. 36a zu <ref-law>; MARANTA/FASSBIND, a.a.O., S. 460; ZOGG, a.a.O.); dessen Vertretungskompetenz fällt weg (<ref-law>), was grundsätzlich zum Alleinvertretungsrecht des anderen Elternteils führt (vgl. AFFOLTER-FRINGELI/VOGEL, a.a.O., N. 36a zu <ref-law>). Im Kontext des Kindesunterhalts wird in der Doktrin auch von einer Interessenkollision des anderen Elternteils ausgegangen, wenn Ehegatten- bzw. nachehelicher Unterhalt in Konkurrenz zum Kindesunterhalt steht (vgl. GEISER, a.a.O., S. 1284) oder wenn Betreuungsunterhalt gefordert wird (GEISER, a.a.O., S. 1288 f.; MARANTA/FASSBIND, a.a.O., S. 457; SCHWEIGHAUSER/STOLL, a.a.O.). Soweit ersichtlich wird dagegen nicht postuliert, es bestehe eine Interessenkollision, wenn es lediglich um den Barunterhalt des Kindes geht. Keine Interessenkollision ist schliesslich im Interesse des fordernden Elternteils zu sehen, selbst weniger Unterhalt in Geld leisten zu müssen, denn diesfalls sind die Interessen des Kindes und jene des klagenden Elternteils gleichgerichtet.
2.7.2. Die in der Doktrin zur Annahme einer Interessenkollision Anlass gebenden Konstellationen können teils nur bei verheirateten bzw. geschiedenen Eltern (Ehegatten- bzw. nachehelicher Unterhalt), teils aber gleichermassen bei nicht bzw. nie miteinander verheirateten Eltern vorkommen (Betreuungsunterhalt).
Sind bzw. waren die Eltern verheiratet, spielt sich der Kindesunterhaltsprozess im Rahmen eines Eheschutzverfahrens (<ref-law>), eines vorsorglichen Massnahmeverfahrens (<ref-law>), eines Scheidungsverfahrens (<ref-law>) oder eines Abänderungsverfahrens (Art. 134 Abs. 2 bzw. Art. 179 Abs. 1 i.V.m. <ref-law> sowie Art. 276 i.V.m. <ref-law>) ab. In diesen eherechtlichen Verfahren (zum Begriff vgl. den 6. Titel der ZPO) stehen sich die Eltern gegenüber und das Kind hat keine eigentliche Parteistellung; es wird von jenem Elternteil vertreten, der für das Kind Unterhalt fordert. In den eherechtlichen Verfahren ist dem Gericht aufgegeben, die Notwendigkeit der Vertretung des Kindes zu "prüfen" und eine solche "wenn nötig" anzuordnen (<ref-law>). Mithin hat der Gesetzgeber für den eherechtlichen Kindesunterhaltsprozess im Normalfall entweder keine relevante Interessenkollision zwischen dem vertretenden Elternteil und dem vertretenen Kind erkannt, oder er hat diese zumindest in Kauf genommen, ansonsten er die Vertretung des Kindes durch einen Beistand zur Regel hätte erklären müssen.
Im selbständigen Kindesunterhaltsprozess ist das Kind Partei und damit seine prozessuale Stellung stärker als im eherechtlichen Verfahren. Wenn das Kind aber im eherechtlichen Verfahren, wo die Gefahr der Interessenkollision nicht nur gleichermassen, sondern noch intensiver lauert, nach dem gesetzgeberischen Willen nicht in jedem Fall eine Vertretung benötigt, so hat dies erst recht für den selbständigen Unterhaltsprozess zu gelten. Es ist in der Tat nicht einzusehen und es werden auch in der Doktrin keine Argumente dafür vorgetragen, weshalb im selbständigen Kindesunterhaltsprozess andere Massstäbe gelten sollten als im eherechtlichen.
2.7.3. Dieses Ergebnis lässt sich auch unter folgenden Gesichtspunkten rechtfertigen: Sowohl im eherechtlichen als auch im selbständigen Kindesunterhaltsprozess gilt die strenge Untersuchungsmaxime, welche das Gericht verpflichtet, den Sachverhalt von Amtes wegen zu erforschen (<ref-law>). Ebenso sind beide Prozesse von der Offizialmaxime beherrscht; das Gericht entscheidet ohne Bindung an die Parteianträge (<ref-law>). Mit anderen Worten hängt das Urteil des Gerichts weder von den Tatsachenbehauptungen der Parteien noch von deren Rechtsbegehren ab und kann das Gericht auf unangemessene Vorbringen bzw. Anträge reagieren. Bereits aus diesen Gründen sind die Interessen des Kindes grundsätzlich genügend geschützt; Handlungsbedarf besteht erst, wenn ein konkreter Interessenkonflikt vorliegt oder die Handlungen des die Vertretung beanspruchenden Elternteils ungenügend erscheinen (vgl. ROELLI, a.a.O.). Anders als in den von der Rechtsprechung bisher behandelten Fällen bleibt eine allfällige Interessenkollision nicht verborgen, sondern sie liegt offen und für alle erkennbar auf dem Tisch (vgl. dazu MARANTA/FASSBIND, a.a.O., S. 458). Ausserdem geht die Unterhaltspflicht gegenüber dem minderjährigen Kind in aller Regel allen anderen familienrechtlichen Unterhaltspflichten vor (<ref-law>; so bereits unter dem alten Recht: <ref-ruling> E. 4.2.2). Mit anderen Worten ist die Konkurrenz zwischen Ehegatten- bzw. nachehelichem Unterhalt und Kindesunterhalt durch das Gesetz mit einer klaren Hierarchisierung geregelt; der Kindesunterhalt geniesst von Gesetzes wegen Priorität. Sodann hat das Kind Anspruch auf Betreuungsunterhalt, wenn es einer persönlichen Betreuung durch einen Elternteil bedarf und es diesem aufgrund der Betreuungsleistung nicht möglich ist, durch Arbeitserwerb für seinen eigenen Lebensunterhalt aufzukommen (<ref-ruling> E. 4.3, 377 E. 7.1.3). Da der Betreuungsunterhalt - und damit die Ermöglichung der persönlichen Betreuung durch einen Elternteil - in erster Linie im Interesse des Kindes liegt, ist in diesem Kontext eine Interessenkollisionsproblematik nicht augenfällig (gl.M. Zogg, a.a.O.). Freilich ist der Betreuungsunterhalt wirtschaftlich für den betreuenden Elternteil bestimmt. Insoweit hat dieser ein eigenes Interesse an den entsprechenden Unterhaltsleistungen; unter Umständen haben sie zur Folge, dass er keine Sozialhilfe beanspruchen muss. Seine Interessen laufen jenen des Kindes aber nicht zuwider. Da der Barunterhalt dem Betreuungsunterhalt vorgeht (<ref-ruling> E. 4.3), tritt die Deckung der Lebenshaltungskosten des betreuenden Elternteils nicht in Konkurrenz zur Finanzierung des Bedarfs des Kindes. Ferner geht es im Rahmen des Betreuungsunterhalts nicht darum, einen anspruchsvollen Lebensstandard des betreuenden Elternteils zu sichern (<ref-ruling> E. 7.1.4).
2.7.4. Im Ergebnis sind im selbständigen Kindesunterhaltsverfahren hinsichtlich der Vertretungsmacht eines Elternteils mit Blick auf Art. 306 Abs. 2 und 3 ZGB die Grundsätze des <ref-law> analog anzuwenden; ein Vertreter des Kindes ist durch das Gericht oder die KESB nur zu bestellen, wenn dies im konkreten Fall notwendig erscheint.
2.8. Der Beschwerdeführer ist denn auch der Meinung, zwischen Kind und Mutter bestehe ein konkreter Interessenkonflikt. Dieser zeichne sich dadurch aus, dass die Beschwerdegegnerin ein Interesse sowohl an der Deckung ihres Barbedarfs als auch an einem regelmässigen Kontakt zum Beschwerdeführer habe; der regelmässige Kontakt werde aber verunmöglicht, wenn der Beschwerdeführer die einverlangten Unterhaltsbeiträge bezahlen müsse. Demgegenüber habe die Mutter lediglich ein Interesse daran, möglichst wenig vom Barbedarf der Beschwerdegegnerin decken zu müssen. Bei dieser Argumentation verliert der Beschwerdeführer aus den Augen, dass das Gericht in seinem Bedarf Besuchsrechtskosten von Fr. 350.-- bzw. Fr. 400.-- berücksichtigt hat. Da diese entgegen seiner Auffassung genügen (vgl. hinten E. 3.4.3), droht nicht wie behauptet der Abbruch der regelmässigen Kontakte und ist dem Argument des Beschwerdeführers hinsichtlich der konkreten Interessenkollision die Grundlage entzogen.
2.9. Zusammengefasst bestand keine Notwendigkeit, der Beschwerdegegnerin einen Beistand für das erstinstanzliche Verfahren (und später das Berufungsverfahren) zu ernennen, nachdem die elterliche Sorge auf beide Eltern übertragen wurde. Die Beschwerde ist in diesem Punkt abzuweisen.
3.
Anlass zur Beschwerde gibt auch die vorinstanzliche Festsetzung des Barunterhaltsbeitrags für die Beschwerdegegnerin.
3.1. Beim Entscheid über den Kindesunterhalt ist der Sachrichter in vielfacher Hinsicht auf sein Ermessen verwiesen (<ref-law>). Ermessensentscheide dieser Art überprüft das Bundesgericht an sich frei; es greift allerdings nur ein, wenn die kantonale Instanz von dem ihr zustehenden Ermessen einen falschen Gebrauch gemacht hat, d.h. wenn sie grundlos von in Lehre und Rechtsprechung anerkannten Grundsätzen abgegangen ist, wenn sie Gesichtspunkte berücksichtigt hat, die keine Rolle hätten spielen dürfen, oder wenn sie umgekehrt rechtserhebliche Umstände ausser Acht gelassen hat. Aufzuheben und zu korrigieren sind ausserdem Ermessensentscheide, die sich als im Ergebnis offensichtlich unbillig, als in stossender Weise ungerecht erweisen (<ref-ruling> E. 4.5; <ref-ruling> E. 11.2; je mit Hinweisen).
3.2. Die Vorinstanz ermittelte zunächst den Barbedarf der Beschwerdegegnerin, indem sie die jeweiligen Bedarfszahlen der Zürcher Kinderkosten-Tabelle (sog. Zürcher Tabellen) vom 1. Januar 2017 für ein Einzelkind (Fr. 1'231.-- [1-6 Jahre], Fr. 1'481.-- [7-12 Jahre] bzw. Fr. 1'781.-- [13-18 Jahre]) mit den Fremdbetreuungskosten (Fr. 400.-- [bis 12 Jahre] bzw. Fr. 160.-- [13-16 Jahre]) ergänzte. Gestützt auf diese Zahlen ging sie in der Folge von einem durchschnittlichen Barbedarf von Fr. 1'800.-- aus, von welchem sie die Familienzulage von Fr. 200.-- abzog.
Für die Kindsmutter ging die Vorinstanz von einem Bedarf von Fr. 3'560.-- (bis Juni 2018) bzw. Fr. 3'220.-- (ab Juli 2018) und einem Einkommen von Fr. 4'750.-- (80 %) aus. Sie bezifferte ihren monatlichen Überschuss mit Fr. 1'220.-- (bis Juni 2018) bzw. Fr. 1'560.-- (ab Juli 2018), wobei sie hier allerdings - wohl aus Versehen - mit einem Einkommen von Fr. 4'780.-- rechnete.
Den Bedarf des Beschwerdeführers bemass die Vorinstanz mit gerundet Fr. 2'200.-- (bis Juli 2017) bzw. Fr. 2'150.-- (ab August 2017). Unter Anrechnung eines hypothetischen Einkommens von Fr. 2'730.-- berechnete sie einen monatlichen Überschuss von Fr. 530.-- (bis Juli 2017) bzw. Fr. 580.-- (ab August 2017). Im Umfang dieses Überschusses verpflichtete sie den Beschwerdeführer dazu, an den Unterhalt der Beschwerdegegnerin beizutragen.
3.3. Der Beschwerdeführer bemängelt die vorinstanzliche Bedarfsrechnung (E. 3.4), die der Kindsmutter und ihm angerechneten Einkommen (E. 3.5) sowie die Verteilung der Unterhaltslast auf die Eltern (E. 3.6).
3.4.
3.4.1. Er moniert, es gehe nicht an, für das Kind die Beträge gemäss Zürcher Tabellen zu verwenden, während er auf dem Existenzminimum lebe. Im Grundsatz ist ihm hier beizupflichten, denn es gilt den Gleichbehandlungsgrundsatz zu beachten (Urteil 5A_743/2017 vom 22. Mai 2019 E. 5.2.3). Es ist nicht zulässig, den unterhaltspflichtigen Elternteil auf das betreibungsrechtliche Existenzminimum zu setzen, während der Kindesbedarf grosszügig bemessen wird. Vorliegend operierte die Vorinstanz indes, was den Beschwerdeführer anbelangt, nicht mit dem betreibungsrechtlichen, sondern mit dem familienrechtlichen Existenzminimum. Dies ergibt sich daraus, dass sie Positionen wie "Versicherung" und "Kommunikation" berücksichtigte, welche beim betreibungsrechtlichen Existenzminimum in den Grundbetrag fallen. Die Rüge des Beschwerdeführers geht diesbezüglich fehl. Berechtigt ist demgegenüber seine Kritik an der vorinstanzlichen Erwägung, zusammengezählt verfügten die Eltern über ein Haushaltseinkommen, welches in die Bandbreite der den Zürcher Tabellen zugrunde liegenden Zahlen (Haushaltsbudgeterhebung) falle, sodass sich eine Anpassung der Tabellenwerte erübrige. Die Haushaltsbudgeterhebung spiegelt die Verhältnisse für einen Haushalt wieder, nicht für zwei. Nichtsdestotrotz ist der Beschwerde in diesem Punkt kein Erfolg beschieden, denn der Beschwerdeführer unterlässt es aufzuzeigen, in welchem Umfang die Tabellenwerte konkret anzupassen gewesen wären.
3.4.2. Hinsichtlich der Besuchsrechtskosten beanstandet der Beschwerdeführer, die Vorinstanz habe nicht berücksichtigt, dass Flugkosten für die Tochter von monatlich Fr. 61.65 sowie erhöhte Lebenshaltungskosten während seiner Besuche in der Schweiz (Fr. 94.50 pro Monat) anfielen. Ob derartige Aufwendungen in die Bedarfsrechnung aufzunehmen sind oder nicht, stellt eine Rechtsfrage dar, während ihre konkrete Höhe eine Tatfrage beschlägt (Urteil 5A_435/2011 vom 14. November 2011 E. 9.2, in: FamPra.ch 2012 S. 192).
Die Vorinstanz nahm die Flugkosten nicht in die Bedarfsrechnung auf mit der Begründung, diese würden von den Eltern des Beschwerdeführers getragen. Dieses Vorgehen ist angesichts des ihr in diesem Bereich zustehenden weiten Ermessens nicht zu beanstanden. Die Grosseltern der Beschwerdegegnerin haben, wie die Vorinstanz feststellte, ein eigenes Interesse an den Reisen des Enkelkindes nach Berlin, da dies auch Kontakte mit ihnen ermöglicht. Die Berücksichtigung ihrer Zuwendungen hat somit nicht deren Zweckentfremdung zur Folge (vgl. <ref-ruling> E. 2c/bb). Der Beschwerdeführer macht nicht geltend, vor Vorinstanz eingewandt zu haben, seine Eltern bezahlten die Flugkosten nicht mehr. Damit gelingt es ihm nicht, die Annahme der Vorinstanz, seine Eltern würden diese Kosten auch in Zukunft weiterhin übernehmen, als offensichtlich unrichtig auszuweisen, und seine diesbezüglichen Rügen der Verletzung von <ref-law> und <ref-law> gehen fehl.
Mit Bezug auf die höheren Lebenshaltungskosten bei Besuchen in der Schweiz erwog die Vorinstanz, eine Erhöhung wäre zwar vertretbar, indes erscheine dies aufgrund der eher tiefen Leistungsfähigkeit des Beschwerdeführers nicht opportun. Indem auf eine währungsbedingte Erhöhung des hypothetischen Einkommens verzichtet worden sei, verfüge der Beschwerdeführer diesbezüglich über einen gewissen Spielraum. Eine Erhöhung würde zudem mittelbar die Interessen der Beschwerdegegnerin beeinträchtigen, indem die für den Kindesunterhalt notwendigen Mittel für die Kosten der Besuchsrechtsausübung verwendet würden, was es zu vermeiden gelte. Der Beschwerdeführer beschränkt sich darauf, seinen von demjenigen der Vorinstanz abweichenden Standpunkt zu bekräftigen. Weshalb falscher Ermessensgebrauch vorliegen soll, tut er damit nicht dar.
3.4.3. Demnach ist im Folgenden vom Kindesbedarf auszugehen, wie er im angefochtenen Entscheid festgesetzt wurde. Zwar ist nicht nachvollziehbar, weshalb die Vorinstanz anstelle der konkreten Zahlen (welche bis zu Fr. 310.-- auseinanderliegen) für die gesamte Zeitspanne bis zum Ausbildungsabschluss der heute erst sechsjährigen Tochter auf einen Durchschnittswert abstellte. Der Beschwerdeführer hat dies indes nicht gerügt, sodass sich das Bundesgericht hierzu nicht vertieft zu äussern braucht. Im Übrigen änderten auch abgestufte Bedarfszahlen an der Höhe der durch ihn zu leistenden Unterhaltsbeiträge nichts (vgl. hinten E. 3.6.3).
3.5.
3.5.1. Der Beschwerdeführer kritisiert, dass die Vorinstanz die Pensumsreduktion der Kindsmutter von 100 % auf 80 % per 1. April 2017 gelten liess, anstatt ihr einen hypothetischen Beschäftigungsgrad von 100 % anzurechnen. Im Zuge der Trennung muss sich der die Obhut übernehmende Elternteil darauf behaften lassen, wenn er bereits während des Zusammenlebens erwerbstätig war (sog. Kontinuitätsprinzip; vgl. <ref-ruling> E. 4.5 und E. 4.7). In Anwendung des Kontinuitätsprinzips wäre der Kindsmutter somit tatsächlich eine Vollzeitstelle anzurechnen. Wie sich nachfolgend zeigen wird, hätte dies jedoch keine Auswirkungen auf die Höhe der vom Beschwerdeführer zu bezahlenden Kinderalimente (vgl. hinten E. 3.6.3), sodass sich eine Auseinandersetzung mit den diesbezüglichen Rügen des Beschwerdeführers erübrigt.
3.5.2. Die Vorinstanz hat dem Beschwerdeführer ein hypothetisches Einkommen von Fr. 2'730.-- angerechnet. Dies ist zulässig, wenn ein Elternteil seine Erwerbskraft nicht voll ausschöpft, sofern zumutbar und möglich ist, das hypothetische Einkommen zu erreichen. Der Beschwerdeführer bestreitet, das von der Vorinstanz angenommene Gehalt erzielen zu können, wobei es sich um eine Tatfrage handelt (<ref-ruling> E. 4 in fine; <ref-ruling> E. 3.2; <ref-ruling> E. 4.2.2.2; je mit Hinweisen). Er macht in diesem Zusammenhang eine Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>) sowie der <ref-law>, Art. 152 und Art. 157 ZPO geltend. Behauptungs- und beweisbelastet für die Höhe des erzielbaren hypothetischen Einkommens wäre die Beschwerdegegnerin gewesen, nicht er selbst. Zudem könne nicht die Rede davon sein, er habe nicht dargetan, weshalb er keine neue Stelle finden könne, denn er habe nicht nur diverse Unterlagen eingereicht, sondern auch die Einholung von Gutachten und Zeugen offeriert.
3.5.3. Im Kindesunterhaltsprozess erforscht das Gericht den Sachverhalt von Amtes wegen (<ref-law>). Dem Beschwerdeführer ist indes insofern beizupflichten, als die Beschwerdegegnerin als fordernde Partei mit Bezug auf das strittige hypothetische Einkommen die Folgen der Beweislosigkeit zu tragen hätte, denn auch im Anwendungsbereich der strengen Untersuchungsmaxime entscheidet das Gericht gemäss <ref-law> nach Beweislastgesichtspunkten (Urteil 5A_59/2016 vom 1. Juni 2016 E. 4.4 mit Hinweis). Entgegen der Auffassung des Beschwerdeführers liegt hier jedoch kein Fall von Beweislosigkeit vor: Die Höhe des ihm angerechneten hypothetischen Einkommens ist das Ergebnis der Beweiswürdigung der Vorinstanz. Diese stützte sich hierzu - wie bereits die Erstinstanz - unter anderem auf die Einnahmen, welche der Beschwerdeführer in der Vergangenheit bei D._ und der E._ erzielt hatte, auf seine eigenen, in einem Bewerbungsschreiben formulierten Gehaltsvorstellungen sowie auf seine eigene Angabe in einer E-Mail, seit Abschluss des Studiums im Bereich der Unternehmenskommunikation zu arbeiten. Ebenso berücksichtigte sie sein Alter, seine Berufserfahrung und seinen Gesundheitszustand. Die Rüge der Verletzung von <ref-law> erweist sich somit als unbegründet.
3.5.4. Ebenfalls fehl geht der Vorwurf, die Vorinstanz habe den Beweisanspruch des Beschwerdeführers verletzt. Nachdem sie gestützt auf obgenannte Beweise und Umstände zur Überzeugung gelangt war, das hypothetische Einkommen sei tatsächlich erzielbar, verzichtete die Vorinstanz in vorweggenommener Beweiswürdigung auf die vom Beschwerdeführer beantragten Zeugeneinvernahmen und Gutachtensaufträge. Weder der Beweisanspruch noch die Untersuchungsmaxime schliessen eine antizipierte Würdigung von Beweisen aus (<ref-ruling> E. 9.3.2 mit Hinweisen; Urteil 5A_59/2016 vom 1. Juni 2016 E. 4.4 mit Hinweis). Eine solche verträgt sich mit den Ansprüchen auf rechtliches Gehör (<ref-law>) bzw. auf Zulassung zum Beweis (<ref-law>) nur dann nicht, wenn der Makel der Willkür an ihr haftet. Der Beschwerdeführer behauptet Willkür nur im Zusammenhang mit der Schlussfolgerung der Vorinstanz, er versuche nicht mit der nötigen Intensität, seine Verdienstmöglichkeiten auszuschöpfen. Es gelingt ihm nicht, aufzuzeigen, weshalb dies angesichts der spärlichen Anzahl dokumentierter Bewerbungen und des unbezahlten Engagements für eine überschuldete Firma offensichtlich unrichtig sein sollte. Auch ist der Vorinstanz kein Vorwurf zu machen, wenn sie darauf hinweist, dass sich die Korrespondenz von Online-Bewerbungen ausdrucken lässt, und deshalb der blossen Behauptung solcher Bewerbungen wenig Gewicht beimisst.
3.5.5. Soweit der Beschwerdeführer eine über den Teilgehalt des Beweisanspruchs hinausgehende Verletzung seines rechtlichen Gehörs geltend machen wollte, substanziiert er diese nicht genügend. Damit bleibt es bei dem ihm angerechneten hypothetischen Einkommen.
3.6.
3.6.1. Es bleibt zu prüfen, ob die Vorinstanz mit den gesprochenen Unterhaltsbeiträgen für die direkten Kinderkosten, welche dem monatlichen (hypothetischen) Überschuss des Beschwerdeführers entsprechen (Fr. 530.-- bis Juli 2017 bzw. Fr. 580.-- ab August 2017), ihr Ermessen in bundesrechtswidriger Weise ausgeübt hat.
3.6.2. Nach <ref-law> wird der Unterhalt eines Kindes durch Pflege, Erziehung und Geldzahlung geleistet (Abs. 1). Die Eltern sorgen gemeinsam, ein jeder nach seinen Kräften, für den gebührenden Unterhalt des Kindes und tragen insbesondere die Kosten von Betreuung, Erziehung, Ausbildung und Kindesschutzmassnahmen (Abs. 2).
Es gilt der Grundsatz, dass der das Kind nicht oder nicht wesentlich betreuende Elternteil bei gegebener Leistungsfähigkeit für dessen gebührenden Unterhalt in Geld aufzukommen hat (Urteile 5A_727/2018 vom 22. August 2019 E. 4.3.2.1 mit Hinweisen; 5A_743/2017 vom 22. Mai 2019 E. 5.1; 5A_339/2018 vom 8. Mai 2019 E. 5.4.2 f. mit Hinweisen). Eine Unterhaltsleistung in Geld setzt indes die entsprechende Leistungsfähigkeit voraus (<ref-law>). Diese ist grundsätzlich in dem Umfang gegeben, als das eigene Einkommen den eigenen Bedarf übersteigt (Urteile 5A_727/2018 vom 22. August 2019 E. 4.3.2.2; 5A_743/2017 vom 22. Mai 2019 E. 5.3.2; je mit Hinweisen). Im Einzelfall kann der Richter ermessensweise auch den (haupt-) betreuenden Elternteil dazu verpflichten, einen Teil des Barbedarfs zu decken, wenn dieser leistungsfähiger ist als der nicht bzw. kaum betreuende Elternteil (Urteile 5A_727/2018 vom 22. August 2019 E. 4.3.2.2 mit Hinweisen; 5A_339/2018 vom 8. Mai 2019 E. 5.4.3 mit Hinweisen; 5A_583/2018 vom 18. Januar 2019 E. 5.1 in fine). Dies rechtfertigt sich namentlich dann, wenn ansonsten die Unterhaltslast für den in bescheidenen Verhältnissen lebenden Unterhaltsschuldner besonders schwer wöge (vgl. <ref-ruling> E. 2.2.2).
3.6.3. Der Beschwerdeführer ist nicht voll leistungsfähig; nach Bezahlung der Unterhaltsbeiträge, welche den Kindesbedarf nicht decken, verbleibt ihm bloss das familienrechtliche Existenzminimum. Die Kindsmutter kommt, indem sie das Manko übernimmt, für (phasenweise deutlich) mehr als die Hälfte des Barbedarfs der Beschwerdegegnerin auf. Ihr steht danach noch ein Überschuss zur Verfügung. Sie trägt aber nebst der Pflege und Erziehung, welche sie als allein Obhutsberechtigte erbringt, bereits substanziell an den Barunterhalt der Tochter bei. Der Vorinstanz kann deshalb kein falscher Ermessensgebrauch vorgeworfen werden, wenn sie der Kindsmutter nebst den in natura erbrachten Leistungen nicht einen noch grösseren Anteil am Kindesunterhalt zuwies. Deren Überschuss ist (auch bei Anrechnung eines 100 %-Pensums) nicht derart bedeutend, dass die Unterhaltspflicht des Beschwerdeführers für diesen im Vergleich eine besondere Härte darstellen würde (vgl. hierzu <ref-ruling>). Der Beschwerde ist auch hier kein Erfolg beschieden.
4.
Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kos-ten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 1 und 2 BGG). Er hat indessen ein Gesuch um unentgeltliche Rechtspflege gestellt. Die gesetzlichen Voraussetzungen hierfür sind erfüllt, sodass seinem Gesuch entsprochen werden kann (Art. 64 Abs. 1 und 2 BGG). Der Beschwerdeführer wird darauf hingewiesen, dass er der Gerichtskasse Ersatz zu leisten hat, wenn er später dazu in der Lage ist (<ref-law>). Da nicht anzunehmen ist, dass die Beschwerdegegnerin die Parteientschädigung beim Beschwerdeführer wird erhältlich machen können, wird ihre Rechtsvertreterin ebenfalls aus der Bundesgerichtskasse entschädigt.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird gutgeheissen und es wird ihm Rechtsanwältin Karin Meyer als Rechtsbeiständin beigegeben.
3.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 4'000.-- zu entschädigen. Die Entschädigung wird indes vorläufig auf die Bundesgerichtskasse genommen und Rechtsanwältin Dr. Petra Rihar wird aus der Bundesgerichtskasse mit Fr. 3'000.-- entschädigt.
5.
Rechtsanwältin Karin Meyer wird aus der Bundesge richtskasse mit Fr. 3'000.-- entschädigt.
6.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 26. August 2019
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Herrmann
Die Gerichtsschreiberin: Gutzwiller