Sachverhalt:
A. Z._ (nachfolgend: Beschwerdegegnerin), geboren am xxxx 1982, serbische Staatsangehörige, kam 1999 in die Schweiz. Im Jahre 2001 heiratete sie X._ (nachfolgend: Beschwerdeführer), geboren am xxxx 1980, serbischer Staatsangehöriger, welcher 2003 in die Schweiz übersiedelte. Zusammengelebt haben die Parteien ab der Übersiedelung des Beschwerdeführers in die Schweiz bis zu dessen Verhaftung im Juli 2004. Seit Januar 2005 arbeitet die Beschwerdegegnerin nicht mehr und hat seither keine neue Arbeitsstelle gefunden.
Mit Eingabe vom 2. Februar 2007 machte die Beschwerdegegnerin beim Bezirksgericht Zürich eine Scheidungsklage hängig und stellte gleichzeitig ein Gesuch um Erlass vorsorglicher Massnahmen. Mit Verfügung vom 12. März 2007 wies die Einzelrichterin des Bezirksgerichts Zürich das vorsorgliche Massnahmebegehren betreffend Unterhalt und Prozesskostenvorschuss ab.
B. Mit Rekurs vom 3. Mai 2007 beantragte die Beschwerdegegnerin dem Obergericht des Kantons Zürich, der Beschwerdeführer sei im Sinne einer vorsorglichen Massnahme zu verpflichten, rückwirkend ab 2. Februar 2006 und für die Dauer des Scheidungsverfahrens Unterhaltsbeiträge von Fr. 1'700.-- pro Monat zu bezahlen.
Mit Beschluss vom 16. Oktober 2008 hiess das Obergericht die Beschwerde teilweise gut und verpflichtete den Beschwerdeführer, der Beschwerdegegnerin ab 5. Februar 2006 bis 31. Dezember 2008 monatliche Unterhaltsbeiträge von je Fr. 1'200.-- zu bezahlen.
C. Mit Beschwerde vom 24. November 2008 beantragt der Beschwerdeführer dem Bundesgericht die Aufhebung des obergerichtlichen Beschlusses und die Bestätigung der erstinstanzlichen Verfügung, eventualiter die Zurückweisung an die Vorinstanz zu neuer Beurteilung. Ferner ersucht er um Gewährung der unentgeltlichen Rechtspflege.
Die Beschwerdegegnerin beantragt in ihrer Vernehmlassung vom 9. Dezember 2008 zum Gesuch um aufschiebende Wirkung ebenfalls die Gewährung der unentgeltlichen Rechtspflege.
Mit Verfügung vom 15. Dezember 2008 wurde der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.
In der Sache schliesst die Beschwerdegegnerin in ihrer Vernehmlassung vom 27. Oktober 2009 auf Abweisung der Beschwerde. Das Obergericht hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. 1.1 Angefochten ist ein Entscheid betreffend eine vorsorgliche Massnahme für die Dauer des Scheidungsverfahrens (<ref-law>) und damit eine Zivilsache i.S.v. <ref-law>. Der Beschluss des Obergerichts ist kantonal letztinstanzlich (<ref-law>), weil er der kantonalen Nichtigkeitsbeschwerde nicht unterliegt (§ 284 Ziff. 7 der Zivilprozessordnung des Kantons Zürich vom 13. Juni 1976 [ZPO/ZH; OS 271]; Urteile 5A_211/2008 vom 7. Juli 2008 E. 1; 5A_253/2007 vom 26. November 2007 E. 4.1), und Endentscheid i.S.v. <ref-law>. Die Streitwertgrenze von Fr. 30'000.-- (<ref-law>) ist erreicht. Die Beschwerde in Zivilsachen ist somit insoweit gegeben.
1.2 Mit der Beschwerde über vorsorgliche Massnahmen kann nur die Verletzung verfassungsmässiger Rechte gerügt werden (<ref-law>). Das Bundesgericht prüft die Verletzung von Grundrechten nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Die erhobenen Rügen müssen zudem in der Beschwerdeschrift selber enthalten sein; der blosse Verweis auf Ausführungen in anderen Rechtsschriften oder auf die Akten reicht nicht aus (<ref-ruling> E. 3.1 S. 399 f. mit Hinweisen).
2. Soweit sich der Beschwerdeführer darauf beruft, dass die Ehe in Serbien bereits im Jahre 2006 geschieden worden sei, ist ihm entgegenzuhalten, dass das Obergericht die Frage der Gültigkeit bzw. Anerkennung des Scheidungsurteils des Amtsgerichts Kragujevac ausdrücklich nicht als Gegenstand des Rekursverfahrens bezeichnet hat. Mit dieser vorinstanzlichen Erwägung setzt sich der Beschwerdeführer nicht auseinander. Vielmehr hat er selbst vor Obergericht ausgeführt, die Frage der Bedeutung des Scheidungsurteils sei nicht Gegenstand des Rekursverfahrens, nachdem die Anerkennung des Scheidungsurteils vor erster Instanz mangels rechtsgenüglicher Vorladung (<ref-law> [SR 291]) verweigert worden war. Insoweit erweist sich die Rüge des Beschwerdeführers als gegenstandslos und ist auf sie nicht einzutreten.
3. Der Beschwerdeführer rügt eine Verletzung des Anspruchs auf Beurteilung innert angemessener Frist (<ref-law>). Er macht geltend, es gehe um die Beurteilung vorsorglicher Massnahmen in einem familienrechtlichen Prozess, welcher bereits als Hauptverfahren gemäss <ref-law>/ZH dem einfachen und raschen Verfahren unterstehe. Der Schriftenwechsel mit der Beschwerdegegnerin sei am 22. Juni 2007 geschlossen worden. Der angefochtene Entscheid sei jedoch erst 16 Monate später ergangen.
Der Beschwerdeführer bringt vor, es seien im vorliegenden Verfahren keine komplexen Rechtsfragen zu klären gewesen und seine Rechtsvertreterin habe verschiedentlich telefonisch nach dem Entscheid nachgefragt, sei jedoch immer wieder nur vertröstet geworden. Aus seinen Ausführungen ergibt sich jedoch nicht, weshalb damit eine Aufhebung des obergerichtlichen Beschlusses zu begründen sein soll.
Weiter führt der Beschwerdeführer an, die Scheidung hätte ohne weiteres bereits im Jahre 2007 ausgesprochen werden können, sodass der Beschwerdegegnerin, welche keine nachehelichen Unterhaltsbeiträge beantragt habe, für das Jahr 2008 keine Unterhaltsbeiträge mehr zugesprochen worden wären. Indes tut er nicht dar, welche Fragen Gegenstand des Scheidungsverfahrens sind und weshalb dieses bereits im Jahr 2007 hätte abgeschlossen werden können.
Insoweit ist auf die Beschwerde mangels genügender Begründung nicht einzutreten.
4. Strittig in der Sache ist, ob die Beschwerdegegnerin zur Geltendmachung von Unterhaltsbeiträgen für die Dauer des Scheidungsverfahrens berechtigt ist.
4.1 Das Obergericht bejahte unter dem Aspekt der ehelichen Gemeinschaft bzw. der ehelichen Solidarität grundsätzlich die Unterhaltspflicht des Beschwerdeführers ab Februar 2006, somit ein Jahr vor Einreichung der Scheidungsklage (s. oben, Sachverhalt Bst. A).
Es führte jedoch aus, dass die Beschwerdegegnerin bis zum Verlust der Arbeitsstelle im Jahre 2005 immer erwerbstätig war. Die Aufgabenteilung während der Ehe im unterhaltsrechtlich relevanten Sinn sei nicht derart lebensprägend gewesen, dass ein Ehegatte deswegen ehebedingte (wirtschaftliche) Nachteile zu verzeichnen gehabt habe. Die Folgen der mit der Eheschliessung verbundenen Aufgabenteilung hätten die wirtschaftliche Selbständigkeit der Beschwerdegegnerin nicht eingeschränkt. Sie mache selbst geltend, dass sie während der Zeit des Zusammenlebens für die gesamten Lebenshaltungskosten aufgekommen sei, mit Ausnahme der Krankenkassenprämien für den Beschwerdeführer.
Der Beschwerdeführer mache geltend, dass die Beschwerdegegnerin, wenn sie sich ordnungsgemäss verhalten hätte, mindestens bis Februar 2007 Arbeitslosenunterstützung erhalten hätte. Ausserdem gehe aus den erstinstanzlichen Akten hervor, dass die Beschwerdegegnerin das Erlöschen eines allfälligen Anspruchs auf Arbeitslosenentschädigung selbst zu vertreten habe. Da sie die Verminderung ihrer Leistungskraft indes nicht rückgängig machen könne, sei ihr kein Erwerbsersatzeinkommen i.S. eines hypothetischen Einkommens rückwirkend anzurechnen.
Da die Beschwerdegegnerin in der Hauptsache mangels lebensprägender Ehe auf die Geltendmachung persönlicher Unterhaltsbeiträge im Sinne von <ref-law> verzichte, habe von Beginn des Verfahrens festgestanden, dass kein nachehelicher Unterhaltsbeitrag zugesprochen werde, und habe die Beschwerdegegnerin seit Januar 2007 gewusst, dass sie alles daran werde setzen müssen, wieder eine Arbeitsstelle zu finden, um ihre wirtschaftliche Selbständigkeit wieder zu erlangen. Sie habe daher nicht davon ausgehen dürfen, dass sie noch über Jahre hinweg Unterhaltsbeiträge werde beanspruchen können, sodass eine Unterhaltsverpflichtung des Beschwerdeführers für die uneingeschränkte Dauer des Scheidungsprozesses als unbillig erschiene und sie daher bis Ende Dezember 2008 zu befristen sei.
4.2 Dagegen wendet der Beschwerdeführer ein, es sei der Beschwerdegegnerin möglich und stets möglich gewesen, für ihren Lebensunterhalt selbst zu sorgen. Aufgrund des gelebten Ehemodells sei es nicht nachvollziehbar, weshalb sie für die Dauer des Scheidungsverfahrens Unterhaltsbeiträge erhalten solle. Entgegen der Auffassung der Vorinstanz seien vorliegend die Grundregeln für den nachehelichen Unterhalt gemäss <ref-law> bereits bei den vorsorglichen Massnahmen für das Getrenntleben einzubeziehen, weil eine Wiederaufnahme des gemeinsamen Haushalts nicht mehr zu erwarten sei.
Die Beschwerdegegnerin habe es selbst zu verschulden, dass sie keine Arbeitsstelle mehr habe. Es sei aktenkundig, dass sie ihre letzte Arbeitsstelle im Jahre 2005 selbst gekündigt und anschliessend die ihr zustehende Arbeitslosenunterstützung nicht eingefordert habe. Es sei rechtsmissbräuchlich und verstosse gegen das Willkürverbot, wenn ihm das Versäumnis der Beschwerdegegnerin, die ihr zustehende Arbeitslosenunterstützung einzufordern, angelastet werde. Der Beschwerdegegnerin sei daher ein Minimallohn in der Höhe ihres Notbedarfs anzurechnen. Aufgrund der geringen Ehedauer wäre die Verpflichtung zur Leistung von Unterhaltsbeiträgen für fast drei Jahre unverhältnismässig. Damit werde <ref-law> verletzt und in willkürlicher Weise auf <ref-law> abgestellt. Auch sei der Unterhaltsbeitrag aufgrund mutwilliger Herbeiführung der Bedürftigkeit als nach <ref-law> unbillig zu betrachten, zumal die Beschwerdegegnerin keine ehebedingten Nachteile erlitten habe.
Ausserdem habe die Vorinstanz Unterhaltsbeiträge für eine Zeit festgelegt, für welche der aktuelle Sachverhalt gar nicht mehr bekannt sei. So hätten sich beide Parteien bereits anlässlich der ersten Hauptverhandlung am 12. März 2007 vor Bezirksgericht Zürich wieder neu orientiert. Er sei bereits wieder neu verheiratet, und auch die Beschwerdegegnerin sei im Zeitpunkt der Verhandlung von einem anderen Manne schwanger gewesen und habe am 11. Mai 2007 ein Kind zur Welt gebracht. Dieser Umstand sei von der Vorinstanz ausser Acht gelassen worden. Ihm könne es nicht zur Last gelegt werden, wenn die Beschwerdegegnerin nun ein aussereheliches Kind geboren und zu betreuen habe. Es sei zu vermuten, dass sie mit ihrem neuen Freund und Vater des Kindes zusammengezogen sei. Des Weiteren müsse auch davon ausgegangen werden, dass sie ein entsprechendes Einkommen generiere, da sie von irgend etwas leben müsse. Damit sei anzunehmen, dass sich die Verhältnisse seit Beendigung des Schriftenwechsels bei der Beschwerdegegnerin geändert hätten, was die Vorinstanz willkürlich ausser Acht gelassen habe, weshalb sie ihn zu Unterhaltsbeiträgen bis Ende 2008 verpflichtet habe. Sollte das Bundesgericht zur Auffassung kommen, dass Unterhaltsbeiträge geschuldet seien, wäre die Sache an die Vorinstanz zurückzuweisen und der Sachverhalt ab Juni 2007 neu abzuklären.
4.3 Die Beschwerdegegnerin bringt im Wesentlichen vor, sie könne die Verminderung ihrer Leistungskraft nicht mehr rückgängig machen. Ohnehin sei die ihr gesetzte Frist von zweieinhalb Monaten zur Erzielung eines hypothetischen Einkommens äusserst kurz. Die Tatsache, dass aller Voraussicht nach kein nachehelicher Unterhalt geschuldet sei, könne bei der Frage der Zumutbarkeit der Wiederaufnahme einer Erwerbstätigkeit massgebend sein; sie vermöge jedoch an der bis zur rechtskräftigen Scheidung fortbestehenden Beistandspflicht nichts zur ändern.
4.4 Nach <ref-law> trifft das Gericht die nötigen vorsorglichen Massnahmen während des Scheidungsverfahrens. Die Bestimmungen über die Massnahmen zum Schutz der ehelichen Gemeinschaft (<ref-law>) sind sinngemäss anwendbar. Gemäss <ref-law> setzt das Gericht die Geldbeträge fest, die der eine Ehegatte dem andern schuldet. Ist eine Wiederherstellung des gemeinsamen Haushaltes nicht mehr zu erwarten, sind die Kriterien für die Bemessung des Scheidungsunterhalts (<ref-law>) analog heranzuziehen, insbesondere was die Frage der Wiederaufnahme oder der Ausdehnung der Erwerbstätigkeit eines Ehegatten betrifft (Urteil 5A_677/2007 vom 21. April 2008 E. 5.1 mit Verweis auf <ref-ruling> E. 3.2 S. 541 f. und 128 III 65 E. 4a S. 67). Insoweit darf dem Ziel der wirtschaftlichen Selbstständigkeit des bisher nicht oder bloss in beschränktem Umfang erwerbstätigen Ehegatten bereits eine gewisse Bedeutung zugemessen werden (<ref-ruling> E. 3.2 S. 542; vgl. auch Urteil 5A_677/2007 vom 21. April 2008 E. 5.1).
4.4 Nach <ref-law> trifft das Gericht die nötigen vorsorglichen Massnahmen während des Scheidungsverfahrens. Die Bestimmungen über die Massnahmen zum Schutz der ehelichen Gemeinschaft (<ref-law>) sind sinngemäss anwendbar. Gemäss <ref-law> setzt das Gericht die Geldbeträge fest, die der eine Ehegatte dem andern schuldet. Ist eine Wiederherstellung des gemeinsamen Haushaltes nicht mehr zu erwarten, sind die Kriterien für die Bemessung des Scheidungsunterhalts (<ref-law>) analog heranzuziehen, insbesondere was die Frage der Wiederaufnahme oder der Ausdehnung der Erwerbstätigkeit eines Ehegatten betrifft (Urteil 5A_677/2007 vom 21. April 2008 E. 5.1 mit Verweis auf <ref-ruling> E. 3.2 S. 541 f. und 128 III 65 E. 4a S. 67). Insoweit darf dem Ziel der wirtschaftlichen Selbstständigkeit des bisher nicht oder bloss in beschränktem Umfang erwerbstätigen Ehegatten bereits eine gewisse Bedeutung zugemessen werden (<ref-ruling> E. 3.2 S. 542; vgl. auch Urteil 5A_677/2007 vom 21. April 2008 E. 5.1).
4.5 4.5.1 Indem das Obergericht der Beschwerdegegnerin die versäumten Arbeitslosenentschädigungen mit der Begründung nicht angerechnet hat, sie könne die Verminderung ihrer Leistungskraft nicht rückgängig machen (s. oben, E. 4.1), hat es sich auf die Rechtsprechung des Bundesgerichts zur Anrechenbarkeit eines hypothetischen Einkommens bezogen, wonach selbst bei Beeinträchtigung der Leistungsfähigkeit in Schädigungsabsicht dem rechtsmissbräuchlich handelnden Ehegatten ein hypothetisches Einkommen nur angerechnet werden darf, wenn er die Verminderung seiner Leistungskraft rückgängig machen kann (<ref-ruling> E. 4a S. 6; <ref-ruling> E. 4a S. 317; vgl. auch Heinz Hausheer und andere, Berner Kommentar, 2. Aufl. 1999, N. 22 und N. 59f zu <ref-law> sowie N. 20 zu <ref-law>, unter Hinweis auf die teilweise nicht veröffentlichte Rechtsprechung des Bundesgerichts; zur Vermögensentäusserung vgl. <ref-ruling> E. 1b S. 17 f.).
4.5.2 Diese Rechtsprechung bezieht sich jedoch auf Fälle, in denen es um die Beurteilung der fortwährenden Leistungsfähigkeit des unterhaltsverpflichteten bzw. -berechtigten Ehegatten geht und damit festzustellen ist, was der Rentenschuldner bzw. -gläubiger seit Einreichung des Gesuchs und während einer längeren Zeitspanne wird leisten können. In diesen Fallkonstellationen muss vom tatsächlichen Zustand ausgegangen und das Einkommen berücksichtigt werden, das der betreffende Ehegatte tatsächlich erzielt, es sei denn, er könnte - und müsste daher - mehr verdienen. Trifft Letzteres zu, ist ihm eine angemessene Frist zur Umsetzung seiner Verpflichtung einzuräumen (<ref-ruling> E. 2.2 S. 420; <ref-ruling> E. 5 S. 17).
4.5.3 Vorliegend geht es jedoch nicht um die Beurteilung der Leistungsfähigkeit der Beschwerdegegnerin für eine längere in der Zukunft liegende Periode. Vielmehr decken die vorsorglich verfügten Unterhaltsbeiträge die Zeit zwischen Februar 2006 (ein Jahr vor Einreichung der Scheidungsklage) bis Ende 2008 ab (s. oben, Sachverhalt Bst. B). Es handelt sich um eine abgeschlossene Zeitspanne: Die Vermögens- und Einkommensverhältnisse, die diese Periode betreffen, wirken sich nur auf sie und nicht auf die Zukunft aus. Mit anderen Worten ist lediglich zu entscheiden, ob die Beschwerdegegnerin, die die fragliche Periode offensichtlich so gut überstanden hat, dass sie in der Zeit eine neue Familie gründen konnte, vom Beschwerdeführer noch rückwirkend Unterhaltsbeiträge erhalten soll, die jedoch keine tatsächlichen Aufwendungen ersetzen oder entschädigen sollen. Es liegt mithin eine andere Ausgangslage vor, auf welche die Rechtsprechung zur Anrechenbarkeit des hypothetischen Einkommens nicht anwendbar ist.
4.5.4 Wenn die Beschwerdegegnerin in der fraglichen Zeit keine eigenen Einkünfte hatte, ist dies ausserdem nur darauf zurückzuführen, dass sie auf ihr zustehende Arbeitslosenentschädigungen verzichtet hatte, indem sie solche gar nicht rechtsgültig eingefordert hatte (s. oben, E. 4.1). Soweit sie vor Bundesgericht vorbringt, der Beschwerdeführer hätte ihr bereits ab ihrem Stellenverlust im Januar 2005 Unterhalt bezahlen sollen, sie habe sich ohne diese Unterhaltsbeiträge offensichtlich in einer Notlage befunden und sei im fraglichen Zeitraum tatsächlich von der Unterstützung durch ihre Eltern abhängig gewesen, bezieht sie sich auf ihre angebliche tatsächliche finanzielle Situation und verkennt, dass es vorliegend um die Anrechenbarkeit versäumter Arbeitslosengelder geht. Ebenfalls ins Leere stösst ihr Einwand, ihr habe zum Zeitpunkt der Geburt ihres Kindes im Frühjahr 2007 und in den ersten Monaten danach nicht zugemutet werden können, einer Erwerbstätigkeit nachzugehen: Der Beschwerdegegnerin ist nicht vorzuhalten, nicht einer Arbeitstätigkeit nachgegangen zu sein, sondern die Arbeitslosenentschädigungen nicht eingefordert zu haben. Weiter bestreitet sie zwar, es selbst verschuldet zu haben, dass sie ab Januar 2005 kein Einkommen mehr erzielt habe; auch könne von einem rechtsmissbräuchlichen Verhalten ihrerseits keine Rede sein. Indes verweist sie in diesem Zusammenhang lediglich auf ihre Ausführungen im kantonalen Verfahren, was den Begründungsanforderungen an eine Beschwerde nicht genügt (s. oben, E. 1.2), sodass darauf nicht einzutreten ist.
4.5.5 Entscheidend ist im vorliegenden Fall somit nicht nur die Freiwilligkeit, mit der die Beschwerdegegnerin ihre Einkommenssituation aufs Spiel gesetzt hat (vgl. Urteil 5C.15/2002 vom 27. Februar 2002 E. 4c, in: FamPra.ch 2002 S. 573), sondern auch der Umstand, dass es sich um eine beschränkte und ohnehin bereits abgeschlossene Zeitspanne handelt und die Beschwerdegegnerin diese Periode offensichtlich wirtschaftlich zu überstehen vermocht hat. Vor diesem Hintergrund hat die Beschwerdegegnerin die Folgen der versäumten Arbeitslosenentschädigungen selbst zu tragen. Das Einfordern von rückständigen Unterhaltsleistungen erscheint unter den gegebenen Umständen in diesem Umfang als rechtsmissbräuchlich.
4.6 Insofern als der Beschwerdegegnerin die versäumten Arbeitslosenentschädigungen nicht angerechnet worden sind, ist der angefochtene Entscheid somit in Begründung und Ergebnis unhaltbar und verstösst daher gegen das Willkürverbot (<ref-law>). Insoweit ist die Beschwerde gutzuheissen und der Beschluss des Obergerichts aufzuheben.
Da sich weder im angefochtenen Entscheid noch in der Beschwerde Angaben zur Höhe und Dauer der versäumten Arbeitslosenentschädigungen finden, kann nicht festgestellt werden, in welchem Umfang sich die Beschwerdegegnerin die versäumten Arbeitslosenentschädigungen anzurechnen hat. Ausserdem hat das Obergericht den Bedarf der Beschwerdegegnerin nicht festgestellt. Die Sache ist daher zur Abklärung dieser Fragen und - gestützt darauf - zur Neubeurteilung der Unterhaltspflicht des Beschwerdeführers an die Vorinstanz zurückzuweisen.
5. Strittig ist weiter die Berechnung des Bedarfs des Beschwerdeführers durch das Obergericht. Der Beschwerdeführer rügt auch in diesem Zusammenhang einen Verstoss gegen das Willkürverbot (<ref-law>).
5.1 Diesbezüglich erwog das Obergericht, es sei für die Steuern lediglich der von der Beschwerdegegnerin anerkannte Betrag von Fr. 100.-- einzusetzen, da in der Unterhaltsberechnung sogar ohne Einbezug der Steuern ein Manko resultieren werde.
Der Beschwerdeführer macht dagegen geltend, ihm seien Steuern in der Höhe von Fr. 350.-- abzuziehen, da er diese tatsächlich bezahlen müsse und die Nichtberücksichtigung höchstens für eine Übergangszeit zu vertreten wäre, wenn tatsächlich ein Erlass oder eine Stundung zu erwarten wäre. Ausserdem habe er für das Jahr 2007 Steuern von insgesamt Fr. 6'970.80 bezahlen müssen, und es sei davon auszugehen, dass die Steuern für das Jahr 2008 gleich hoch seien.
Wie der Beschwerdeführer selbst ausführt, war ihm bewusst, dass nach der bundesgerichtlichen Rechtsprechung in finanziell knappen Fällen, wo das eheliche Einkommen zur Deckung des Grundbedarfes zweier Haushalte nicht ausreicht, die Steuerpflicht des Rentenschuldners bei der Berechnung seines familienrechtlichen Grundbedarfes grundsätzlich nicht zu berücksichtigen ist (<ref-ruling> E. 2b S. 70, 289 E. 2a/bb S. 292; <ref-ruling> E. 1a/aa S. 356). Er weist lediglich auf die Kritik von Vetterli hin (Rolf Vetterli, in: FamKomm Scheidung, 2005, N. 33 zu <ref-law>). Angesichts der klaren, publizierten Praxis vermag dieser Hinweis die Annahme eines Verstosses gegen das Willkürverbots durch das Obergericht keinesfalls zu begründen.
5.2 Sodann führte das Obergericht aus, dem Beschwerdeführer seien als Fahrtauslagen lediglich die Auslagen für den öffentlichen Verkehr von Fr. 75.-- einzusetzen, da ein Arbeitsweg von etwas über einer halben Stunde - insbesondere angesichts der engen finanziellen Verhältnisse - als zumutbar erscheine.
Der Beschwerdeführer wendet ein, ihm seien die Autokosten für den Fahrtweg anzurechnen, da diese faktisch angefallen seien, ihm ein mehrmaliges Umsteigen nicht zumutbar sei und er in der Vergangenheit habe darauf vertrauen können, dass er nicht noch zusätzlich Unterhaltsbeiträge zahlen müsse.
Indes hat das Obergericht die Zumutbarkeit des Arbeitswegs - insbesondere auch im Hinblick auf die finanziellen Verhältnisse der Parteien - berücksichtigt, sodass ihm auch diesbezüglich keine Willkür vorzuwerfen ist.
5.3 Schliesslich hielt das Obergericht fest, die vom Beschwerdeführer geltend gemachten Gesundheitskosten von Fr. 100.-- seien nicht belegt und daher nicht in den Bedarf aufzunehmen.
Demgegenüber vertritt der Beschwerdeführer die Auffassung, die Gesundheitskosten seien ebenfalls im Notbedarf zu berücksichtigen, da dieser Betrag nicht überhöht sei und der Betrag für die Krankenversicherung sehr tief angesetzt sei.
Er bestreitet jedoch nicht, dass er diesen Betrag im kantonalen Verfahren nicht belegt hat, und legt auch nicht dar, weshalb ihm Gesundheitskosten in dieser Höhe entstanden sein sollen. Daher stösst seine Willkürrüge auch insofern ins Leere.
6. 6.1 Zusammenfassend ist die Beschwerde insofern gutzuheissen, als sie sich auf Anrechenbarkeit der seitens der Beschwerdegegnerin versäumten Arbeitslosenentschädigungen bezieht. Die Sache ist zur Feststellung ihrer Höhe und Dauer, zur Feststellung des Bedarfs der Beschwerdegegnerin sowie zur Neubeurteilung der Unterhaltspflicht des Beschwerdeführers an das Obergericht zurückzuweisen. Im Übrigen ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
Das Obergericht wird über die kantonalen Kosten- und Entschädigungsfolgen neu zu befinden haben.
6.2 Angesichts des teilweisen Unterliegens des Beschwerdeführers sowie des offenen Ausgangs des kantonalen Verfahrens ist praxisgemäss die Gerichtsgebühr vor Bundesgericht den Parteien je zur Hälfte aufzuerlegen und sind die Parteikosten wettzuschlagen, sodass jede Partei die eigenen Parteikosten für das bundesgerichtliche Verfahren selbst trägt (Art. 66 Abs. 1 und Art. 68 Abs. 1 BGG).
6.3 Da der Beschwerdeführer seine Bedürftigkeit genügend belegt hat und die Bestellung eines Rechtsbeistands zur Wahrung seiner Rechte notwendig ist, ist sein Gesuch um unentgeltliche Prozessführung und Verbeiständung für das bundesgerichtliche Verfahren gutzuheissen (Art. 64 Abs. 1 und 2 BGG).
Die Beschwerdegegnerin führt zur Begründung ihres Gesuchs um unentgeltliche Rechtspflege lediglich aus, die zu erwartende Parteientschädigung sei angesichts des Gesuchs des Beschwerdeführers vermutlich uneinbringlich. Dies genügt zum Nachweis der Bedürftigkeit jedoch nicht, sodass sich ihr Gesuch als unbegründet erweist und daher abzuweisen ist.
6.4 Damit ist der hälftige Anteil des Beschwerdeführers an den Gerichtskosten einstweilen auf die Bundesgerichtskasse zu nehmen und seiner Vertreterin aus der Bundesgerichtskasse eine reduzierte Entschädigung von Fr. 800.-- zu entrichten.
Die Beschwerdegegnerin trägt ihren hälftigen Anteil an der Gerichtsgebühr sowie ihre Parteientschädigung für das bundesgerichtliche Verfahren selbst. Insoweit wird das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren gegenstandslos.

Demnach erkennt das Bundesgericht:
1. In Gutheissung des Eventualantrags wird der Beschluss vom 16. Oktober 2008 des Obergerichts des Kantons Zürich aufgehoben. Die Sache wird im Sinne der Erwägungen zu neuer Beurteilung sowie zur Neuverlegung der Kosten und Entschädigungen des kantonalen Verfahrens an das Obergericht zurückgewiesen.
Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird gutgeheissen, soweit es nicht gegenstandslos geworden ist. Ihm wird Rechtsanwältin Rachel Grütter als amtliche Rechtsbeiständin beigegeben.
Das Gesuch der Beschwerdegegnerin um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden den Parteien je zur Hälfte auferlegt. Der Anteil des Beschwerdeführers an den Gerichtskosten von Fr. 1'000.-- wird einstweilen auf die Bundesgerichtskasse genommen.
4. Die Parteikosten werden wettgeschlagen.
5. Rechtsanwältin Rachel Grütter wird für ihre Bemühungen im bundesgerichtlichen Verfahren ein reduziertes Honorar von Fr. 800.-- aus der Bundesgerichtskasse entrichtet.
6. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 2. März 2010
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Rapp