Sachverhalt: A. X._ (geb. 1959) und Z._ (geb. 1963) heirateten im Oktober 1990. Sie wurden Eltern von drei Kindern (geb. in den Jahren 1991, 1994 und 1995). Mit Urteil vom 4. Mai 2006 schied das Bezirksgericht Zürich die Ehe und beliess die drei Kinder antragsgemäss unter der gemeinsamen elterlichen Sorge der Parteien. Es genehmigte die von den Parteien eingereichte Scheidungskonvention über die Nebenfolgen der Scheidung und nahm diese in das Urteilsdispositiv auf. Was den Kinderunterhalt betrifft, verpflichtete sich X._, indexierte Unterhaltsbeiträge von je Fr. 1'000.-- pro Monat ab Rechtskraft des Scheidungsurteils bis zur Mündigkeit beziehungsweise bis zum Abschluss der Erstausbildung jedes Kindes, jeweils zuzüglich allfällige vertragliche und/oder gesetzliche Kinderzulagen, zu bezahlen (Ziff. 3.5 des Scheidungsurteils). B. Mit Klage vom 25. Juni 2009 beantragte der anwaltlich vertretene X._ dem Bezirksgericht Zürich, die Kinderunterhaltsbeiträge gemäss Ziff. 3.5 des Scheidungsurteils vom 4. Mai 2006 seien "angemessen abzuändern"; eine allfällige Bezifferung bleibe bis zum Abschluss des Beweisverfahrens vorbehalten. Das Bezirksgericht wies die Abänderungsklage mit Urteil vom 10. August 2012 ab. C. C.a Dagegen erhob X._ am 20. September 2012 Berufung an das Obergericht des Kantons Zürich. Seine Rechtsbegehren in der von seiner (nach wie vor gleichen) Rechtsanwältin verfassten Berufung lauteten wie folgt: "1. Das angefochtene Urteil vom 10. August 2012 des Bezirksgerichts Zürich (Prozess Nr. ...) sei aufzuheben und die Abänderungsklage sei insofern gutzuheissen, als die in Dispositiv-Ziff. 3.5 des Scheidungsurteils des Bezirksgerichts Zürich vom 4. Mai 2006 festgesetzten Kinderunterhaltsbeiträge angemessen abzuändern seien. 1.a) Eventualiter sei das Verfahren im Sinne von Art. 327 Abs. 3 lit. a ZPO [sic!] an die Vorinstanz zur Durchführung eines Beweisverfahrens zurückzuweisen." Zudem ersuchte er um unentgeltliche Rechtspflege und Verbeiständung für das Berufungsverfahren. C.b Mit Beschluss vom 12. Oktober 2012 trat das Obergericht auf die Berufung nicht ein und wies das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wegen Aussichtslosigkeit der Berufung ab. D. Dem Bundesgericht beantragt X._ (nachfolgend Beschwerdeführer) in seiner Beschwerde in Zivilsachen vom 19. November 2012, der obergerichtliche Beschluss vom 12. Oktober 2012 sei aufzuheben, die Sache zur materiellen Behandlung an das Obergericht zurückzuweisen und ihm die unentgeltliche Rechtspflege und Verbeiständung für das Berufungsverfahren zu gewähren. Zudem ersucht der Beschwerdeführer auch für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege und Verbeiständung. Das Bundesgericht hat die Vorakten eingeholt. Z._ (nachfolgend Beschwerdegegnerin) und das Obergericht haben je mit Schreiben vom 22. Januar 2013 auf eine Vernehmlassung verzichtet. 