Sachverhalt:
A.
A.a. A._ (geb. 1966; Beschwerdeführer) und B._ (geb. 1977; Beschwerdegegnerin) sind die nicht miteinander verheirateten Eltern von C._ (geb. 2010).
In der Vereinbarung vom 30. Juli 2011 verpflichtete sich A._, für seinen Sohn bis zum Abschluss einer angemessenen Ausbildung, mindestens aber bis zur Mündigkeit, monatlichen Unterhalt von Fr. 1'000.-- zu bezahlen. Dieser Unterhaltsvertrag wurde durch die Sozialbehörde U._ genehmigt.
A.b. Mit Klage vom 19. Oktober 2016 ersuchte A._ das Bezirksgericht Bülach um die Aufhebung bzw. die Reduktion der Unterhaltspflicht ab Klageeinreichung. Am 25. April 2017 wies das Bezirksgericht sowohl ein Gesuch von A._ um Erlass vorsorglicher Massnahmen wie auch ein solches um unentgeltliche Rechtspflege ab. Die von A._ hiergegen eingelegten Rechtsmittel blieben erfolglos (vgl. Urteil 5A_888/2017 vom 8. Januar 2018). An der Hauptverhandlung vom 11. September 2017 beantragte A._ ausserdem die Regelung des persönlichen Verkehrs mit seinem Sohn.
Mit Urteil vom 1. März 2018 regelte das Bezirksgericht den persönlichen Verkehr zwischen Vater und Sohn und errichtete für Letzteren eine Besuchsrechtsbeistandschaft. Das Begehren von A._ um Anpassung der Unterhaltsbeiträge wies es ab.
B.
Auf Berufung von A._ hin regelte das Obergericht mit Urteil vom 16. Oktober 2018 (eröffnet am 18. Oktober 2018) den persönlichen Verkehr zwischen Vater und Sohn neu und ordnete für das Kind eine Besuchsrechtsbeistandschaft mit angepasstem Inhalt an. Im Übrigen bestätigte es das Urteil des Bezirksgerichts und damit auch die Abweisung der Klage auf Abänderung des Kindesunterhalts. Mit Beschluss von demselben Datum trat das Obergericht ausserdem auf einen Antrag von A._ um unentgeltliche Rechtspflege für das erstinstanzliche Verfahren nicht ein und wies das entsprechende Gesuch für das Berufungsverfahren ab.
C.
Mit Beschwerde in Zivilsachen vom 12. November 2018 gelangt A._ mit dem Antrag ans Bundesgericht, in Anpassung des Urteils vom 16. Oktober 2018 sei seine Pflicht zur Leistung von Unterhaltsbeiträgen an den Sohn aufzuheben. Eventualiter sei die Sache "zwecks Fassung eines unterhaltsbezogenen neuen Entscheids entsprechend den Weisungen des Bundesgerichts" an das Obergericht oder das Bezirksgericht zurückzuweisen. Ausserdem sei A._ sowohl für das Verfahren vor dem Obergericht als auch für das Verfahren vor dem Bundesgericht gänzlich von den Gerichtskosten zu befreien und es sei ihm für beide Verfahren ein unentgeltlicher Rechtsbeistand zu bestellen.
Mit Eingabe vom 19. November 2018 äussert sich A._ ergänzend zur Sache und reicht neue Beweismittel ein. Mit Eingabe vom 4. Juni 2019 ersucht er ausserdem um die beförderliche Behandlung seiner Beschwerde.
Das Bundesgericht hat die Akten des kantonalen Verfahrens, indes keine Vernehmlassungen eingeholt.

Erwägungen:
1.
1.1. Angefochten ist der Endentscheid (<ref-law>) einer letzten kantonalen Instanz, die als oberes Gericht (<ref-law>) über die Abänderung der Unterhaltspflicht gegenüber einem minderjährigen Kind und damit eine vermögensrechtliche Zivilsache (<ref-law>) entschieden hat (vgl. etwa Urteil 5A_90/2017 vom 24. August 2017 E. 1.1). Der nach Art. 74 Abs. 1 Bst. b BGG erforderliche Streitwert von Fr. 30'000.-- ist erreicht (Art. 51 Abs. 1 Bst. a und Abs. 4 BGG). Die Beschwerde in Zivilsachen ist das zutreffende Rechtsmittel. Der Beschwerdeführer ist nach <ref-law> zur Beschwerde berechtigt. Die Beschwerde und deren Ergänzung sind innert Frist eingereicht worden (<ref-law>). Unter Vorbehalt der nachfolgenden Ausführungen ist auf die Beschwerde einzutreten.
1.2. Mit der Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 f. BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>) und prüft mit freier Kognition, ob der angefochtene Entscheid Recht verletzt. Es befasst sich aber nur mit formell ausreichend begründeten Einwänden (vgl. <ref-law>). In der Beschwerdebegründung ist daher in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid rechtswidrig sein soll. Die Begründung muss sachbezogen sein und sich auf den Streitgegenstand beziehen und beschränken; die beschwerdeführende Partei hat in gezielter Auseinandersetzung mit den für das Ergebnis des angefochtenen Entscheids massgeblichen Erwägungen plausibel aufzuzeigen, welche Rechte bzw. Rechtsnormen die Vorinstanz verletzt haben soll (<ref-ruling> E. 1.7.1; <ref-ruling> E. 2, 115 E. 2).
An einer hinreichenden Begründung fehlt es insoweit, als der Beschwerdeführer ohne Auseinandersetzung mit dem angefochtenen Urteil allein unter Hinweis auf seine Ausführungen im vorinstanzlichen Verfahren unter dem Titel "Persönlicher Verkehr/Besuchsrecht" die "Frage nach einer Obhutsumteilung" aufwirft. Auf die Beschwerde ist insoweit nicht einzutreten.
1.3. Was den Sachverhalt angeht, legt das Bundesgericht seinem Urteil die vorinstanzlichen Feststellungen zugrunde (vgl. <ref-law>). Diesbezüglich kann die rechtsuchende Partei nur vorbringen, die vorinstanzlichen Feststellungen seien offensichtlich unrichtig, das heisst willkürlich (<ref-law>), oder würden auf einer anderen Bundesrechtsverletzung im Sinn von <ref-law> (z.B. Verletzung von <ref-law> oder <ref-law>) beruhen. In der Beschwerde ist überdies darzutun, inwiefern die Behebung der gerügten Mängel für den Ausgang des Verfahrens entscheidend sein kann (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Es gilt das strenge Rügeprinzip nach <ref-law>. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen, während es auf ungenügend substanziierte Rügen und rein appellatorische Kritik am Sachverhalt nicht eintritt (vgl. zum Ganzen <ref-ruling> E. 1.3.1, 317 E. 5.4; <ref-ruling> E. 2.3). Wird eine Verletzung des Willkürverbots geltend gemacht, reicht es nicht aus, die Lage aus der eigenen Sicht darzulegen und den davon abweichenden angefochtenen Entscheid als willkürlich zu bezeichnen. Es ist im Einzelnen darzutun, inwiefern das kantonale Gericht willkürlich entschieden haben soll und der angefochtene Entscheid deshalb an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.4.1; <ref-ruling> E. 2.2).
Der Beschwerdeführer legt unter dem Titel "Sachverhalt" die Beziehung zum Sohn sowie den Gang des bisherigen Verfahrens aus seiner Sicht dar, ohne dem Obergericht diesbezüglich eine (offensichtlich) unrichtige Sachverhaltsfeststellung vorzuwerfen. Damit genügt die Beschwerde insoweit den Rüge- und Begründungsanforderungen nicht. Soweit der Beschwerdeführer sich von den tatsächlichen Feststellungen der Vorinstanz entfernt, bleiben seine Ausführungen daher unbeachtlich. Auch soweit er sich zu seinem Einkommen in der hier interessierenden Zeitperiode äussert, beschränkt der Beschwerdeführer sich darauf, in appellatorischer Art und Weise seine Sicht der Dinge darzulegen, und unterlässt er es, dem Obergericht eine im Zusammenhang mit der Sachverhaltsfeststellung zu berücksichtigende Rechtsverletzung vorzuwerfen. Eine willkürliche bzw. qualifiziert unrichtige Sachverhaltsfeststellung macht der Beschwerdeführer sodann zwar geltend im Zusammenhang mit der Berechnung seines Bedarfs, mit einem Nebeneinkommen der Beschwerdegegnerin und mit der Frage, welches Einkommen ihm zu erzielen möglich wäre. Auch insoweit beschränkt er sich indes im Wesentlichen auf die Darlegung seines Standpunktes bzw. seiner eigenen Ansichten. Unzulässig sind sodann die verschiedenen Hinweise auf Stellungnahmen aus dem kantonalen Verfahren (vgl. <ref-ruling> E. 1.2.3). Auf die Beschwerde ist auch insoweit nicht einzutreten.
1.4. Neue Tatsachen und Beweismittel dürfen vor Bundesgericht nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Inwiefern dies der Fall ist, ist in der Beschwerde näher dazulegen (vgl. <ref-law>). Hiervon erfasst sind unechte Noven, also Tatsachen, die im bisherigen Verfahren bereits hätten vorgebracht werden können, aber nicht vorgebracht wurden. Echte Noven, d.h. Tatsachen, die erst entstanden sind, nachdem vor der Vorinstanz keine neuen Tatsachen und Beweismittel mehr vorgetragen werden konnten, sind im Verfahren vor Bundesgericht demgegenüber unbeachtlich (<ref-ruling> E. 1.2; <ref-ruling> E. 3.1.2). Vorbehalten bleibt der Fall, dass echte Noven nicht die materielle Beurteilung der Beschwerde, sondern prozessuale Aspekte im Verfahren vor dem Bundesgericht betreffen (Urteile 5A_702/2018 vom 1. Februar 2019 E. 2; 2C_50/2017 vom 22. August 2018 E. 3.1).
Mit der ergänzenden Eingabe vom 19. November 2018 legt der Beschwerdeführer seine aktuelle finanzielle Situation dar und bringt hierzu verschiedene Beweismittel bei, die fast ausschliesslich nach dem angefochtenen Entscheid datieren. Diese echten Noven können nach dem Ausgeführten im Zusammenhang mit dem Gesuch um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren, nicht aber mit der in der Sache strittigen Abänderung der Unterhaltsbeiträge berücksichtigt werden. Gleiches gilt, soweit der Beschwerdeführer unechte Noven vorbringt, da er nicht begründet, weshalb diese heute noch berücksichtigt werden sollten.
2.
2.1. Der Beschwerdeführer macht eine Verletzung des Anspruchs auf rechtliches Gehör geltend, weil das Obergericht seine Stellungnahmen vom 15. und 16. Oktober 2018 nicht berücksichtigt habe. Mit diesen habe er auf die Ausführungen der Beschwerdegegnerin vom 24. September 2018 repliziert, welche ihm am 3. Oktober 2018 zur Kenntnis gebracht worden seien. Es habe ihm offen gestanden, sich innert zehn Tage zu dieser zu äussern. Das Ende der Zehntagesfrist sei auf einen Samstag gefallen, womit sich die Frist bis am Montag, 15. Oktober 2018, verlängert habe. Das Obergericht hätte daher die in der Sache relevanten Eingaben und die mit diesen eingebrachten Beweismittel berücksichtigen müssen, was es indes nicht getan habe.
Dem angefochtenen Entscheid lässt sich diesbezüglich entnehmen, dass die Beschwerdegegnerin am 24. September 2018 eine Stellungnahme samt Beilagen ins Recht legte. Ein Doppel dieser Eingabe hat das Obergericht dem Beschwerdeführer zur Kenntnisnahme zugestellt. Weitere Eingaben der Parteien seien nicht erfolgt. Aus den vorinstanzlichen Akten ergibt sich, dass der Beschwerdeführer die Eingabe vom 24. September 2018 wie geltend gemacht am 3. Oktober 2018 entgegengenommen hat (Akten Obergericht, act. 129). Mit Stellungnahmen vom 15. und am 16. Oktober 2018 hat er hierauf reagiert. Diese Schreiben sind am 17. Oktober 2018 und damit ein Tag nach Ausfällung des angefochtenen Urteils beim Obergericht eingegangen (Akten Obergericht, act. 132 und 134).
2.2. Aus dem Anspruch auf rechtliches Gehör (Art. 6 Ziff. 1 EMRK; <ref-law>; <ref-law>) ergibt sich das Recht der Parteien, von allen dem Gericht eingereichten Stellungnahmen Kenntnis zu erhalten und sich dazu zu äussern (<ref-ruling> E. 4.1.1 mit zahlreichen Hinweisen). Es obliegt daher dem Gericht, den Parteien ein effektives Replikrecht zu gewähren. Hierfür kann es ihnen eine Frist zur Stellungnahme ansetzen. Jedoch genügt es zur Wahrnehmung des Gehörsanspruchs grundsätzlich, dass das Gericht die Stellungnahmen den Parteien zur Information (Kenntnisnahme, Orientierung) zustellt, wenn von ihnen erwartet werden kann, dass sie unaufgefordert Stellung nehmen. Dies ist namentlich bei anwaltlich vertretenen oder rechtskundigen Parteien der Fall. Nach der Zustellung zur Kenntnisnahme ist das Gericht gehalten, mit dem Entscheid eine angemessene Zeitspanne zuzuwarten. Im Sinne einer Faustregel hat es im Allgemeinen zumindest zehn Tage verstreichen zu lassen und kann es erst danach von einem Verzicht auf das Replikrecht ausgehen. Die Wartefrist für das Gericht schliesst die Zeit ein, welche die Partei zur Übermittlung ihrer (Replik-) Eingabe benötigt (zum Ganzen: Urteile 1B_340/2018 vom 18. Oktober 2018 E. 2.3; 5A_41/2018 vom 18. Juli 2018 E. 2.1; 4A_431/2017 vom 2. Mai 2018 E. 4.3; 8C_229/2017 vom 25. Januar 2018 E. 4.1, in: RDAF 2018 I S. 40; je mit Hinweisen).
2.3. Das Obergericht wartete nach Eintreffen der Eingabe der Beschwerdegegnerin beim Beschwerdeführer 13 Tage, bis es sein Urteil fällte. Umstände, weshalb es dem Beschwerdeführer nicht hätte möglich sein sollen, innert dieses Zeitraums Stellung zu nehmen oder zumindest um Ansetzung einer Äusserungsfrist zu ersuchen, sind nicht ersichtlich. Gegenteiliges vermag der Beschwerdeführer auch nicht aus dem Umstand abzuleiten, dass er bereits zu früheren Eingaben der Beschwerdegegnerin Stellung genommen hatte: Das Obergericht brachte durch die blosse Zustellung der Eingabe der Beschwerdegegnerin zur Kenntnisnahme gerade zum Ausdruck, dass es die Sache als spruchreif erachtete und keine weitere Äusserung mehr erwartete. Dies musste dem anwaltlich vertretenen Beschwerdeführer bewusst sein, weshalb eine umgehende Reaktion hätte erwartet werden können (vgl. Urteil 5D_81/2015 vom 4. April 2016 E. 2.3.2, in: FamPra.ch 2016 S. 739 mit Hinweisen). Auch verkennt der Beschwerdeführer die Rechtsprechung, wenn er geltend macht, für die Wahrung der "Frist" von zehn Tagen komme es darauf an, wann er seine Eingabe der Post übergeben habe, und das Gericht hätte noch einige zusätzliche Tage auf die Ankunft der Sendung warten müssen. Vielmehr ist allein entscheidend, bis wann das Gericht von der (Replik-) Eingabe Kenntnis erhält, womit in der zehntägigen Wartefrist die Zeit für deren Übermittlung enthalten ist (E. 2.2 hiervor). Der vorliegende Fall ist gerade nicht so zu behandeln, wie wenn das Gericht eine (zehntägige) Frist zur Vernehmlassung angesetzt hätte (ausführlich: Urteil 5D_81/2015 vom 4. April 2016 E. 2.3.4, in: FamPra.ch 2016 S. 739). Unter diesen Umständen kann keine Verletzung des Anspruchs auf rechtliches Gehör festgestellt werden.
3.
3.1. Im Zusammenhang mit der Anpassung der Unterhaltsbeiträge ist die Höhe der dem Beschwerdeführer anrechenbaren Kosten für die Ausübung des Besuchsrechts umstritten.
Das Obergericht erwog diesbezüglich, der Beschwerdeführer mache geltend, es seien ihm nicht nur USD 450.-- im Monat anzurechnen, sondern die effektiven anfallenden Kosten von jährlich insgesamt Fr. 7950.--. Die pauschalen Vorbringen des Beschwerdeführers würden aber den gesetzlichen Begründungsanforderungen nicht genügen. Insbesondere setze er sich weder mit der vorinstanzlichen Berechnung der Besuchsrechtskosten auseinander, noch mache er geltend, wie sich die effektiven Kosten zusammensetzen sollten, oder belege er diese Kosten. Zu den Begründungsanforderungen führt das Obergericht aus, in der Berufungsschrift sei hinreichend genau aufzuzeigen, inwiefern der erstinstanzliche Entscheid in den angefochtenen Punkten fehlerhaft sei bzw. an einem der gerügten Mängel leide. Dies setze voraus, dass der Berufungskläger die angefochtenen vorinstanzlichen Erwägungen bezeichne und sich mit diesen auseinandersetze. Auch sei mittels klarer und sauberer Verweisungen auf die Ausführungen der Erstinstanz aufzuzeigen, wo die massgebenden Behauptungen, Erklärungen, Bestreitungen und Einreden erhoben worden seien. Weder sei eine pauschale Verweisung auf die bei der Erstinstanz eingereichten Rechtsschriften ausreichend, noch eine neuerliche Darstellung der Sach- und Rechtslage, welche nicht auf das vor der Erstinstanz Vorgebrachte eingehe. Pauschale Hinweise auf frühere Rechtsschriften seien namentlich dann ungenügend, wenn die Erstinstanz sich mit den Ausführungen des Berufungsklägers auseinandergesetzt habe.
3.2. Nach Ansicht des Beschwerdeführers haben seine Ausführungen vor Obergericht den Begründungsanforderungen genügt. Er verweist auf die Darlegungen in der Berufungsschrift, wonach das Bezirksgericht die Anrechnung der Besuchsrechtskosten bestätigt habe, jedoch nicht im Umfang der geltend gemachten "effektiven Kosten". Zur Begründung seines Standpunkts habe der Beschwerdeführer ausdrücklich auf eine im bezirksgerichtlichen Verfahren eingereichte Aufstellung "mit der rechnerischen Herleitung des Kindesunterhalts" verwiesen, welche auch die Besuchsrechtskosten enthalte. Die Berechnung der Besuchskosten sei sodann in einer weiteren Eingabe vom 27. November 2017 detailliert wiedergegeben. In der Berufung seien insbesondere die Flug- und Hotelkosten mit einem aktuellen Beispiel belegt. Die Besuchsrechtskosten liessen sich damit wie in der Berufung wiedergegeben mit wenig Aufwand aufgrund der Verweisung auf die Eingabe vom 27. November 2017 eruieren. Das Obergericht habe sich mit diesem Vorbringen indes nicht auseinandergesetzt und damit den Sachverhalt unrichtig festgestellt.
Diese Ausführungen lassen das angefochtene Urteil nicht als bundesrechtswidrig erscheinen: Anders als der Beschwerdeführer zu meinen scheint, steht im vorliegenden Zusammenhang nicht die Feststellung des Sachverhalts in Frage. Vielmehr stellt sich die (Rechts-) Frage, ob die Berufung ausreichend begründet war (vgl. <ref-law>). Insoweit setzt der Beschwerdeführer sich nicht hinreichend mit den Ausführungen des Obergerichts auseinander: Vorab äussert er sich nicht zu den im angefochtenen Urteil ausführlich dargelegten Anforderungen an die Begründung der Berufungsschrift, womit auf diese nicht weiter einzugehen ist. Sodann zeigt er nicht auf, dass er sich nach diesem Massstab entgegen der Einschätzung des Obergerichts ausreichend mit dem erstinstanzlichen Urteil auseinandergesetzt hätte. Vielmehr macht er einzig geltend, er habe vor Obergericht unter Hinweis auf Eingaben im bezirksgerichtlichen Verfahren (erneut) seine eigene Berechnung der fraglichen Kosten dargelegt. Damit erfüllt er aber die Anforderungen gerade nicht, welche das Obergericht an die Begründung der Berufung stellte. Insbesondere zeigt der Beschwerdeführer damit nicht auf, dass er sich mit der erstinstanzlichen Berechnung der Besuchskosten detailliert auseinandergesetzt hätte.
4.
Nach dem Ausgeführten vermag der Beschwerdeführer die Erwägungen der Vorinstanz zu seinem Einkommen und zum ihm anrechenbaren Bedarf auch insoweit nicht in Frage zu stellen, als seine Vorbringen überhaupt den an eine Beschwerde in Zivilsachen zu stellenden Begründungsanforderungen genügen. Damit sind seine Überlegungen zu einem von ihm angeblich zu tragenden Manko und der sich hieraus ergebenden Notwendigkeit zur Anpassung seiner Unterhaltspflicht - sie beruhen auf Grundlagen, die vom nicht zu beanstandenden Urteil der Vorinstanz abweichen - von vornherein unbehelflich. Gleiches gilt für die Rüge, die Vorinstanz verletzte das Recht auf Familienleben (Art. 8 Ziff. 1 EMRK; <ref-law>), weil sie es dem Beschwerdeführer durch überhöhte Unterhaltsbeiträge faktisch verunmögliche, das ihm eingeräumte Besuchsrecht auszuüben.
Unter diesen Voraussetzungen besteht kein Anlass, auf die vorinstanzliche Kostenregelung oder den Entscheid des Obergerichts über das vom Beschwerdeführer im Berufungsverfahren gestellte Gesuch um unentgeltliche Rechtspflege zurückzukommen. Zumal der Beschwerdeführer sich nicht weiter mit den diesbezüglichen Ausführungen des Obergerichts auseinandersetzt (vgl. vorne E. 1.2).
5.
Zusammenfassend erweist sich die Beschwerde als unbegründet und ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Der obsiegenden Beschwerdegegnerin sind mangels Einholens einer Vernehmlassung keine ersatzpflichtigen Kosten entstanden, sodass keine Parteientschädigung zu sprechen ist (Art. 68 Abs. 1 und 2 BGG). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege ist abzuweisen, da die Beschwerde nach dem Ausgeführten als von Anfang an aussichtslos beurteilt werden muss (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren wird abgewiesen.
3.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien (der Beschwerdegegnerin inkl. Eingabe vom 4. Juni 2019) und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 6. Juni 2019
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Herrmann
Der Gerichtsschreiber: Sieber