Sachverhalt:
A. X._ (Beschwerdeführer) und Z._ (Beschwerdegegnerin) heirateten am xxxx 1983. Sie wurden Eltern des Sohnes S._, geboren am xxxx 1985, und der Tochter T._, geboren am xxxx 1995. Die Parteien trennten sich 2003. Die Folgen des Getrenntlebens wurden gerichtlich geregelt.
Im Oktober 2005 erhob die Beschwerdegegnerin Scheidungsklage und anlässlich der Sühnverhandlung im November 2005 einigten sich die Parteien auf ein gemeinsames Scheidungsbegehren. Das Bezirksgericht Zürich schied die Ehe mit Urteil vom 20. Juli 2007. Es stellte die Tochter T._ - der Teilvereinbarung über die Scheidungsfolgen entsprechend - unter die elterliche Sorge der Beschwerdegegnerin und regelte das Besuchsrecht. Den Beschwerdeführer verpflichtete es zu monatlichen, indexierten Unterhaltsbeiträgen an die Tochter T._ einerseits, und zwar von Fr. 1'200.-- ab Rechtskraft des vorliegenden Urteils bis 31. Oktober 2007 und von Fr. 1'350.-- ab 1. November 2007 bis zum ordentlichen Abschluss einer angemessenen Ausbildung (jeweils zuzüglich Kinderzulagen), und an die Beschwerdegegnerin andererseits, und zwar im Umfang von Fr. 800.-- ab Rechtskraft des vorliegenden Urteils bis 30. November 2013.
Der Beschwerdeführer heiratete nach Rechtskraft des Scheidungspunkts seine neue Lebenspartnerin. Aus dieser Beziehung war bereits zuvor die Tochter U._, geboren am xxxx 2006, hervorgegangen.
B. Am 3. August 2007 erklärte die Beschwerdegegnerin Berufung. Sie forderte - neben einer Änderung der Besuchsrechtsregelung - eine Erhöhung des nachehelichen Unterhalts, focht jedoch den Kindesunterhaltsbeitrag nicht an. Am 29. August 2007 erklärte auch der Beschwerdeführer Berufung. Am 21. Januar 2008 erstattete der Beschwerdeführer Berufungsantwort und beantragte, die Berufung der Beschwerdegegnerin abzuweisen und das Urteil vom 20. Juli 2007 vollumfänglich zu bestätigen. Hingegen reichte der Beschwerdeführer trotz Aufforderung, Berufungsanträge zu stellen und seine eigene Berufung zu begründen, keine entsprechende Rechtsschrift ein, weshalb das Obergericht des Kantons Zürich mit Beschluss vom 19. Februar 2008 auf seine Berufung nicht eintrat.
Mit Urteil vom 16. Dezember 2008 regelte das Obergericht das Besuchsrecht, bestätigte den von keiner Partei angefochtenen Unterhaltsbeitrag für die Tochter von monatlich Fr. 1'350.--, zuzüglich Zulagen, ab Rechtskraft dieses Urteils bis zum ordentlichen Abschluss einer angemessenen Ausbildung. Es bestätigte auch den Unterhaltsbeitrag für die Beschwerdegegnerin von monatlich Fr. 800.-- ab Rechtskraft dieses Urteils bis 30. November 2013. Für die Zeit danach bis zum Eintritt des Beschwerdeführers in das ordentliche Pensionsalter per Ende März 2026 legte es den monatlichen Unterhaltsbeitrag an die Beschwerdegegnerin auf Fr. 560.-- fest, behielt aber eine Erhöhung auf Fr. 1'912.-- vor ab dem Zeitpunkt, in dem die Unterhaltspflicht des Beschwerdeführers gegenüber der Tochter endet.
Gegen die Regelung des nachehelichen und des Kindesunterhalts erhob der Beschwerdeführer kantonale Nichtigkeitsbeschwerde, die vom Kassationsgericht mit Zirkulationsbeschluss vom 13. November 2009 gutgeheissen wurde. Es wies die Angelegenheit an das Obergericht zurück.
Mit Urteil vom 22. Februar 2010 bestätigte das Obergericht die Beitragspflicht des Beschwerdeführers an den Unterhalt der Tochter von monatlich Fr. 1'350.--, zuzüglich Zulagen, ab Rechtskraft dieses Urteils bis zum ordentlichen Abschluss einer angemessenen Ausbildung. Es bestätigte den Unterhaltsbeitrag für die Beschwerdegegnerin von monatlich Fr. 800.-- ab Rechtskraft dieses Urteils bis 30. November 2013 und ordnete an, dass ab 1. Dezember 2013 der Unterhaltsbeitrag entfällt, solange der Beschwerdeführer für die Tochter Unterhaltsbeiträge bezahlen muss. Ab dem Zeitpunkt, in dem seine Unterhaltspflicht gegenüber der Tochter infolge der Vollendung ihrer Erstausbildung endet, wurde der Beschwerdeführer verpflichtet, der Beschwerdegegnerin einen monatlichen Unterhaltsbeitrag von Fr. 927.-- bis 31. März 2026 zu bezahlen.
Die Beschwerdegegnerin erhob daraufhin hinsichtlich ihres nachehelichen Unterhaltsbeitrags kantonale Nichtigkeitsbeschwerde. Der Beschwerdeführer wandte sich gegen Kindes- und nachehelichen Unterhalt mit Beschwerde an das Bundesgericht. Mit Zirkulationsbeschluss vom 20. Mai 2011 hiess das Kassationsgericht die Nichtigkeitsbeschwerde gut. Das Bundesgericht schrieb daraufhin das Rechtsmittel des Beschwerdeführers als gegenstandslos ab (Verfügung 5A_247/2010 vom 5. August 2011).
Mit Urteil vom 16. Januar 2012 bestätigte das Obergericht erneut die Beitragspflicht des Beschwerdeführers an den Unterhalt der Tochter von monatlich Fr. 1'350.--, zuzüglich Zulagen, ab Rechtskraft dieses Urteils bis zum ordentlichen Abschluss einer angemessenen Ausbildung. Es bestätigte auch den Unterhaltsbeitrag für die Beschwerdegegnerin von monatlich Fr. 800.-- ab Rechtskraft dieses Urteils bis 30. November 2013 und ordnete erneut an, dass ab 1. Dezember 2013 der Unterhaltsbeitrag entfällt, solange der Beschwerdeführer für die Tochter Unterhaltsbeiträge bezahlen muss. Ab dem Zeitpunkt, in dem seine Unterhaltspflicht gegenüber der Tochter infolge der Vollendung ihrer Erstausbildung endet, wurde der Beschwerdeführer verpflichtet, der Beschwerdegegnerin einen monatlichen Unterhaltsbeitrag von Fr. 927.-- bis 31. März 2026 zu bezahlen.
C. Am 17. Februar 2012 hat der Beschwerdeführer gegen das obergerichtliche Urteil vom 16. Januar 2012 Beschwerde an das Bundesgericht erhoben. Er beantragt dessen Aufhebung in Bezug auf die Regelung des Kindes- und nachehelichen Unterhalts. Er sei zu verpflichten, einen monatlichen Kindesunterhaltsbeitrag von Fr. 888.05, zuzüglich Zulagen, zu bezahlen. Mangels Leistungsfähigkeit sei der Beschwerdegegnerin kein nachehelicher Unterhalt zuzusprechen. Zudem ersucht er um unentgeltliche Rechtspflege und Verbeiständung.
Das Obergericht hat auf Vernehmlassung verzichtet. Die Beschwerdegegnerin ersucht um Abweisung der Beschwerde und um unentgeltliche Rechtspflege und Verbeiständung.

Erwägungen:
1. Gegen das eine Unterhaltssache (<ref-law>) betreffende angefochtene Urteil der auf Rechtsmittel hin urteilenden oberen kantonalen Instanz (<ref-law>) ist die Beschwerde in Zivilsachen zulässig. Auf die rechtzeitig erhobene Beschwerde ist einzutreten.
2. 2.1 Der Beschwerdeführer wendet sich dagegen, dass ihn die Vorinstanz über seine Leistungsfähigkeit hinaus zu Unterhaltszahlungen verpflichtet hat.
2.2 Die Vorinstanz hat den Bedarf des Beschwerdeführers für sich und seine neue Familie auf Fr. 5'087.20 bestimmt. Sein durchschnittliches monatliches Einkommen betrage Fr. 6'014.35, womit Fr. 927.15 für Unterhaltsleistungen verblieben. Das Obergericht hat sodann ausgeführt, der Beschwerdeführer habe in seiner Berufungsantwort ausdrücklich den Antrag gestellt, die Berufung der Beschwerdegegnerin abzuweisen und das erstinstanzliche Urteil vom 20. Juli 2007 vollumfänglich zu bestätigen. Er habe somit die erstinstanzlich festgesetzten Unterhaltsverpflichtungen nicht angefochten und er sei an diese Parteierklärung gebunden. Er bleibe deshalb verpflichtet - wie bereits erstinstanzlich festgesetzt - an den Unterhalt der Tochter T._ monatliche Beiträge von Fr. 1'350.-- zuzüglich Kinderzulagen zu bezahlen. Des Weiteren habe er - wiederum in Übereinstimmung mit dem erstinstanzlichen Urteil - der Beschwerdegegnerin nachehelichen Unterhalt im Umfang von monatlich Fr. 800.-- bis 30. November 2013 zu bezahlen. Mangels Leistungsfähigkeit des Beschwerdeführers entfalle der Unterhaltsbeitrag an die Beschwerdegegnerin ab 1. Dezember 2013 für solange, als er der Tochter Unterhalt zu bezahlen habe. Ende seine Unterhaltspflicht gegenüber der Tochter, habe er der Beschwerdegegnerin ab diesem Zeitpunkt bis zu seinem Eintritt ins ordentliche gesetzliche Pensionsalter (Ende März 2026) monatlich Fr. 927.-- zu bezahlen.
3. 3.1 Das bezirksgerichtliche Urteil vom 20. Juli 2007 wurde den Parteien am 26. Juli 2007 zugestellt (E. I.2 S. 10 des angefochtenen Urteils). Die am 1. Januar 2011 in Kraft getretene Schweizerische Zivilprozessordnung (ZPO, SR 272) war damit weder auf das Klageverfahren noch auf die anschliessenden Rechtsmittelverfahren anwendbar (Art. 404 f. ZPO). Damit bleibt auf das Scheidungsverfahren das bisherige Recht anwendbar, d.h. massgeblich sind die auf 1. Januar 2011 ausser Kraft getretenen Bestimmungen von aArt. 135-149 ZGB (AS 1999 1132 ff.).
3.2 Vorliegend hat die unterhaltsberechtigte Beschwerdegegnerin den erstinstanzlich festgesetzten nachehelichen Unterhalt vor Obergericht angefochten. Der Beschwerdeführer hat zwar zunächst Kindes- und nachehelichen Unterhalt angefochten und konkrete Berufungsanträge und die Begründung für später in Aussicht gestellt (act. 98 der obergerichtlichen Akten), diese dann jedoch nicht eingereicht, worauf das Obergericht auf seine Berufung nicht eingetreten ist. Sie bleibt deshalb im Folgenden ausser Betracht.
Gemäss aArt. 148 Abs. 1 ZGB hemmt die Einlegung des Rechtsmittels den Eintritt der Rechtskraft nur im Umfang der Anträge; wird jedoch der Unterhaltsbeitrag für den Ehegatten angefochten, so können auch die Unterhaltsbeiträge für die Kinder neu beurteilt werden (vgl. nunmehr <ref-law>). Diese Ausnahmebestimmung bewirkt, dass bei einer Anfechtung des Unterhaltsbeitrags für den Ehegatten von Gesetzes wegen auch die Rechtskraft hinsichtlich der Unterhaltsbeiträge für die Kinder aufgeschoben wird. Dabei kommt es nicht darauf an, ob der unterhaltsverpflichtete oder der unterhaltsberechtigte Ehegatte das ordentliche Rechtsmittel gegen die Regelung des nachehelichen Unterhalts ergriffen hat (Verfügung 5A_247/2010 vom 5. August 2011 E. 3.2; vgl. DANIEL STECK, in: Basler Kommentar, Zivilgesetzbuch, 3. Aufl. 2006, N. 18 f. zu [a]<ref-law>; STÉPHANE SPAHR, in: Commentaire romand, Code civil, 2010, N. 22 f. zu [a]<ref-law>). Das Obergericht hat insoweit zu Recht nicht nur den Ehegattenunterhalt beurteilt, sondern auch die erstinstanzliche Festlegung des Kindesunterhalts als nicht rechtskräftig erachtet, selber noch einmal darüber befunden und einen entsprechenden Beitrag im Dispositiv zugesprochen.
3.3 Der Unterhaltsanspruch der Ehegatten unterliegt der Dispositionsmaxime (<ref-ruling> E. 2.1.2 S. 420; Urteil 5A_441/2008 vom 29. Dezember 2008 E. 4.5, in: Pra 2009 Nr. 66 S. 434 und FamPra.ch 2009 S. 470). Mithin greift das Verschlechterungsverbot (Verbot der reformatio in peius). Dieses besagt, dass die Rechtsmittelinstanz das angefochtene Urteil nicht zu Ungunsten der rechtsmittelführenden Partei abändern darf, es sei denn, die Gegenpartei habe ebenfalls ein Rechtsmittel ergriffen (<ref-ruling> E. 2.1.1 S. 419). Da nach dem Nichteintreten auf die Berufung des Beschwerdeführers einzig die Berufung der Beschwerdegegnerin gegen die bezirksgerichtliche Festsetzung des nachehelichen Unterhalts zu behandeln war, erscheint es demgemäss grundsätzlich richtig, wenn die Vorinstanz der Beschwerdegegnerin nicht weniger zugesprochen hat, als ihr bereits vom Bezirksgericht zugestanden worden war. Auf diese Frage wird allerdings im Zusammenhang mit der Koordination mit dem Kindesunterhalt zurückzukommen sein (s. unten).
Im Gegensatz zum Ehegattenunterhalt unterliegt der Kindesunterhalt der Offizialmaxime; der Richter ist folglich an Parteianträge nicht gebunden und entscheidet selbst bei deren Fehlen (<ref-ruling> E. 3.1 S. 412 mit Hinweisen; vgl. nunmehr <ref-law>). Zudem gilt das Verschlechterungsverbot nicht (<ref-ruling> E. 2.1.1 S. 420; Urteil 5A_652/2009 vom 18. Januar 2010 E. 3.1). Entgegen der Ansicht des Obergerichts ist die Offizialmaxime somit nicht nur zugunsten, sondern auch zulasten des Kindes anzuwenden bzw. zugunsten des Unterhaltspflichtigen (<ref-ruling> E. 3.2.1 S. 414 [zum eng mit der Offizialmaxime zusammenhängenden Untersuchungsgrundsatz]; SPÜHLER/FREI-MAURER, Berner Kommentar, 1991, N. 33 zu [a]<ref-law>; FABIENNE HOHL, Procédure civile, Tome II, 2. Aufl. 2010, Rz. 2091; NICOLAS JEANDIN, in: CPC, Code de procédure civile commenté, 2011, N. 16 zu <ref-law>; a.A. BÜHLER/SPÜHLER, Berner Kommentar, 3. Aufl. 1980, N. 33 zu [a]<ref-law>; FRANK/ STRÄULI/MESSMER, Kommentar zur zürcherischen Zivilprozessordnung, 3. Aufl. 1997, N. 15 zu <ref-law>/ZH). Dies gilt nicht nur dann, wenn sich der Rechtsmittelrichter aufgrund entsprechender Anträge mit dem Kindesunterhalt zu befassen hat, sondern auch dann, wenn er sich lediglich aufgrund von aArt. 148 Abs. 1 ZGB damit auseinandersetzen muss (SPAHR, a.a.O., N. 20 zu [a]<ref-law>; DENIS TAPPY, in: CPC, Code de procédure civile commenté, 2011, N. 14 zu <ref-law> [mit der Einschränkung, dass es sich um eine "Kann-Vorschrift" handle und der Richter auf eine Senkung des Kindesunterhalts verzichten könne]; zweifelnd ROLAND FANKHAUSER, in: Sutter-Somm und andere [Hrsg.], Kommentar zur Schweizerischen Zivilprozessordnung [ZPO], 2010, N. 21 zu <ref-law>). Das Zusammentreffen von Kinder- und Ehegattenrente und insbesondere die in aArt. 148 Abs. 1 ZGB zum Ausdruck gebrachte gegenseitige Abhängigkeit der Unterhaltsbeiträge sowie die Begrenzung beider durch die Leistungsfähigkeit des Pflichtigen ändern daran nichts. Der unterhaltsberechtigte Ehegatte und das Kind verfügen über selbständige Ansprüche mit je eigenem rechtlichem Schicksal. Namentlich bedeutet dies, dass der Ehegattenunterhalt auch im Anwendungsbereich von aArt. 148 Abs. 1 ZGB von der Dispositionsmaxime beherrscht bleibt und der Kindesunterhalt von der Offizialmaxime (zum Ganzen <ref-ruling> E. 2.1.1 und 2.1.2 S. 419 f.). Auch wenn der Gesetzgeber aArt. 148 Abs. 1 ZGB in erster Linie zugunsten des Kindes geschaffen haben mag (vgl. Botschaft vom 15. November 1995 über die Änderung des ZGB, BBl 1996 I 149 Ziff. 234.111), enthält die Norm keine Einschränkung, dass der Kindesunterhalt nur erhöht, nicht aber gesenkt werden dürfte. Das Gesetz äussert sich zudem nicht zur Frage eines allfälligen Vorrangs des Unterhalts für minderjährige Kinder vor dem Ehegattenunterhalt, oder umgekehrt (<ref-ruling> E. 2.3 S. 211 mit Hinweisen), so dass im vorliegenden Kontext davon auszugehen ist, dass ein Konflikt zwischen den beiden Unterhaltsforderungen anhand der dargestellten prozessualen Prinzipien zu lösen ist. Da der Unterhaltspflichtige in jedem Fall von einem Eingriff in sein Existenzminimum geschützt bleibt (<ref-ruling>), führt die Anwendung der genannten Grundsätze dazu, dass im Rahmen der Unterhaltsverpflichtungen bis 30. November 2013 einzig der Kindesunterhalt gesenkt werden kann. Entsprechendes gilt auch für die Phase ab 1. Dezember 2013, in der der Beschwerdeführer nur zu Kindesunterhaltszahlungen verpflichtet wurde. In beiden Phasen ist allerdings zu berücksichtigen, dass alle unterhaltsberechtigten Kinder eines Elternteils im Verhältnis zu ihren objektiven Bedürfnissen finanziell gleich zu behandeln sind. Dabei kann der wiederverheiratete Unterhaltsschuldner die Sicherung des Existenzminimums nur für seine eigene Person beanspruchen, nicht aber für seine gesamte zweite Familie (<ref-ruling> E. 4.2 S. 62 ff.). Die Vorinstanz hat dies nicht berücksichtigt, sondern das Existenzminimum des Schuldners an den Bedürfnissen seiner zweiten Familie ausgerichtet. Es ist demnach noch offen, ob der obergerichtlich festgesetzte Kindesunterhalt tatsächlich gesenkt werden muss. Die Beschwerde ist insoweit gutzuheissen und die Angelegenheit zur neuen Berechnung des Kindesunterhaltsbeitrags an die Vorinstanz zurückzuweisen. Nicht einzugehen ist hingegen auf die letzte Phase der Unterhaltsverpflichtung, d.h. auf die Zeitspanne vom Ende der Unterhaltspflicht gegenüber der Tochter T._ bis 31. März 2026, in der der Beschwerdeführer zu nachehelichem Unterhalt von Fr. 927.-- verurteilt wurde. Der Beschwerdeführer setzt sich mit dieser Phase nicht auseinander und stellt insoweit keine konkreten bzw. nachvollziehbaren Anträge. Soweit sich seine Behauptung, zwischenzeitlich sei sein Einkommen weiter gesunken und seine Leistungsfähigkeit betrage nur noch Fr. 888.05, auch auf diese Phase beziehen sollte, so kann auf seine neuen Tatsachenbehauptungen (Lohnausweis vom 6. Februar 2012) ohnehin nicht eingetreten werden (<ref-law>).
4. Bei diesem Ausgang des Verfahrens rechtfertigt es sich, auf die Erhebung von Gerichtskosten zu verzichten (<ref-law>). Die Parteien tragen ihre jeweiligen Parteikosten selber (<ref-law>). Beide Parteien haben um unentgeltliche Rechtspflege und Verbeiständung ersucht (<ref-law>). Soweit die Gesuche nicht als gegenstandslos abgeschrieben werden, sind sie gutzuheissen. Dem Beschwerdeführer wird Rechtsanwalt Carmine Baselice und der Beschwerdegegnerin Rechtsanwalt Renzo Guzzi beigeordnet. Den Rechtsvertretern wird eine angemessene Entschädigung aus der Bundesgerichtskasse entrichtet. Die Parteien haben der Gerichtskasse hiefür Ersatz zu leisten, wenn sie später dazu in der Lage sein sollten. Über die bisherigen kantonalen Kosten und Entschädigungen wird das Obergericht im Rahmen des Rückweisungsverfahrens zu entscheiden haben (Art. 67, 68 Abs. 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und das Urteil des Obergerichts des Kantons Zürich, I. Zivilkammer, vom 16. Januar 2012 hinsichtlich der Kindesunterhaltsregelung und der Kosten des kantonalen Verfahrens aufgehoben. Die Angelegenheit wird an das Obergericht zur Behandlung im Sinne der Erwägungen zurückgewiesen. Im Übrigen wird auf die Beschwerde nicht eingetreten.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen, soweit es nicht als gegenstandslos abzuschreiben ist. Ihm wird Rechtsanwalt Carmine Baselice als amtlicher Rechtsbeistand beigegeben.
3. Das Gesuch der Beschwerdegegnerin um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen, soweit es nicht als gegenstandslos abzuschreiben ist. Ihr wird Rechtsanwalt Renzo Guzzi als amtlicher Rechtsbeistand beigegeben.
4. Es werden keine Gerichtskosten erhoben.
5. Rechtsanwalt Baselice wird für das bundesgerichtliche Verfahren ein Honorar von Fr. 1'000.-- aus der Bundesgerichtskasse entrichtet.
6. Rechtsanwalt Guzzi wird für das bundesgerichtliche Verfahren ein Honorar von Fr. 1'000.-- aus der Bundesgerichtskasse entrichtet.
7. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 18. Juli 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Zingg