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 <ref-law> [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.

Erwägungen:
1. 1.1 Angefochten ist der Endentscheid eines oberen Gerichts, das auf Rechtsmittel hin kantonal letztinstanzlich über die Abänderung von Kinderunterhaltsbeiträgen gemäss <ref-law> (i.V.m. <ref-law>) und damit in einer Zivilsache entschieden hat (Art. 90, Art. 75 und Art. 72 Abs. 1 BGG). Die gesetzliche Streitwertgrenze in dieser vermögensrechtlichen Angelegenheit kann als erfüllt gelten (<ref-law>). Die im Übrigen fristgerecht (Art. 100 Abs. 1 i.V.m. <ref-law>) eingereichte Beschwerde in Zivilsachen ist grundsätzlich zulässig.
1.2 Der abweisende obergerichtliche Entscheid über das Gesuch um unentgeltliche Rechtspflege und Verbeiständung für das Berufungsverfahren bildet gleichermassen ein taugliches Anfechtungsobjekt (Urteil 5A_396/2009 vom 5. August 2009 E. 1.2, nicht publ. in: <ref-ruling>).
2. 2.1 Der Beschwerdeführer macht geltend, es sei nicht gesetzeskonform, wenn im obergerichtlichen Entscheid als Referent der Gerichtsschreiber und nicht einer der drei gemäss Rubrum mitwirkenden Oberrichterinnen und -richter "getagt" habe. Da er insoweit auf die erste (Zusammensetzung des Gerichts) und letzte Seite (Unterzeichnung nur durch den Gerichtsschreiber) des angefochtenen Entscheids verweist, scheint er beanstanden zu wollen, dass nur der Gerichtsschreiber den angefochtenen Entscheid unterzeichnet hat.
2.2 Die Organisation der Gerichte und der Schlichtungsbehörden ist Sache der Kantone, soweit das Gesetz nichts anderes bestimmt (<ref-law>). Das kantonale Recht bestimmt, wer einen Entscheid zu unterzeichnen hat (SEILER, Die Berufung nach der Schweizerischen Zivilprozessordnung, 2011, N. 1610).
2.3 Das Bundesgericht prüft die Anwendung kantonalen Rechts - vorbehältlich der in Art. 95 lit. c und d BGG genannten Fälle - bloss auf Willkür hin (<ref-law>; <ref-ruling> E. 3.1 S. 227). Für die Verletzung von Grundrechten gilt das Rügeprinzip: Der Beschwerdeführer muss präzise angeben, welches verfassungsmässige Recht verletzt wurde und substanziiert anhand der Erwägungen des angefochtenen Entscheids darlegen, worin die Verletzung besteht (<ref-law>; <ref-ruling> E. 2.2 S. 246). Bei einer Rüge der willkürlichen Anwendung von kantonalem Recht hat der Beschwerdeführer zudem die kantonale Bestimmung, gegen die das Obergericht verstossen haben soll, zu bezeichnen (<ref-ruling> E. 2.1 S. 3; 110 I a 1 E. 2a S. 3 f.).
2.4 Diesen Anforderungen genügt die Rüge des Beschwerdeführers mit dem Hinweis auf den "nicht gesetzeskonformen" Entscheid nicht. Darauf ist nicht einzutreten.
3. 3.1 Das Obergericht ist auf die Berufung des Beschwerdeführers mangels bezifferter Berufungsanträge nicht eingetreten. Es hat erwogen, weder aus dem Antrag noch aus der Berufungsbegründung werde ersichtlich, auf welchen Betrag die Kinderunterhaltsbeiträge herabzusetzen seien, zumal der Beschwerdeführer ausdrücklich darlege, dass er eine angemessene Reduktion und keine "Abänderung auf Null" beantrage.
3.2 Der Beschwerdeführer macht vor Bundesgericht geltend, seiner Berufungsbegründung sei mehr als deutlich zu entnehmen, dass er eine "Abänderung auf Null", das heisst die Aufhebung der Unterhaltspflicht gegenüber seinen Kindern, verlangt habe. Seine zur Begründung der Abänderungsklage dargelegte finanzielle Situation lasse gar keinen anderen Schluss zu. Auch die kantonalen Instanzen hätten seine Begehren so interpretiert, seien sie doch von einem Streitwert von Fr. 336'000.-- ausgegangen. Das Bezirksgericht habe diese Streitwertberechnung damit begründet, dass die drei Kinder voraussichtlich studieren würden und deshalb die Unterhaltspflicht jeweils bis zum 25. Altersjahr bestehen bleibe, was bei einem Unterhaltsbeitrag von je Fr. 1'000.-- pro Monat insgesamt Fr. 336'000.-- ausmache.
Der Beschwerdeführer bringt vor, das Vorgehen des Obergerichts sei widersprüchlich, überspitzt formalistisch (<ref-law>) und verletze Art. 311 und <ref-law>. Zudem sei das Obergericht der Fragepflicht gemäss <ref-law> nicht nachgekommen.
Der Beschwerdeführer bringt vor, das Vorgehen des Obergerichts sei widersprüchlich, überspitzt formalistisch (<ref-law>) und verletze Art. 311 und <ref-law>. Zudem sei das Obergericht der Fragepflicht gemäss <ref-law> nicht nachgekommen.
3.3 3.3.1 Ob Berufungsanträge zu stellen und im Falle von auf Geldzahlung gerichteten Begehren zu beziffern sind, hat das Bundesgericht in <ref-ruling> geklärt.
3.3.2 Demnach muss die Berufungseingabe (<ref-law>) Rechtsbegehren enthalten. Ein Rechtsbegehren muss so bestimmt sein, dass es im Falle der Gutheissung unverändert zum Urteil erhoben werden kann. Stellt der Berufungskläger Anträge in der Sache, müssen die auf Geldzahlung gerichteten Berufungsanträge beziffert werden. Dies gilt auch, soweit wie beim Kinderunterhalt die Offizialmaxime (<ref-law>) anwendbar ist.
Werden unbezifferte Berufungsanträge gestellt, ist auf die Berufung nicht einzutreten, ohne dass dem Berufungskläger eine Nachfrist nach Art. 132 Abs. 1 und 2 ZPO einzuräumen wäre.
Die Rechtsfolge des Nichteintretens auf unbezifferte Begehren steht jedoch unter dem Vorbehalt des überspitzten Formalismus (<ref-law>). Auf eine Berufung mit formell mangelhaften Rechtsbegehren ist ausnahmsweise einzutreten, wenn sich aus der Begründung, allenfalls in Verbindung mit dem angefochtenen Entscheid ergibt, was der Berufungskläger in der Sache verlangt oder - im Falle zu beziffernder Rechtsbegehren - welcher Geldbetrag zuzusprechen ist (vgl. zum Ganzen <ref-ruling> E. 4 ff. S. 618 ff.; Urteile 4A_587/2012 vom 9. Januar 2013 E. 2; 5A_105/2012 vom 9. März 2012 E. 3.2, in: FamPra.ch 2012 S. 811).
4. 4.1 Der Beschwerdeführer forderte in seiner Berufungseingabe vom 20. September 2012 im Hauptantrag, die im Scheidungsurteil festgesetzten Kinderunterhaltsbeiträge seien "angemessen abzuändern" (vgl. Lit. C.a oben). Er stellte demnach einen Antrag in der Sache, ohne jedoch bestimmte und im Falle einer blossen Reduktion (statt vollumfänglichen Aufhebung) der Unterhaltspflicht bezifferte Begehren zu stellen.
4.2 4.2.1 Das Obergericht hat deshalb zutreffend versucht, den unbestimmten Antrag anhand der Berufungsbegründung auszulegen.
4.2.2 Der Beschwerdeführer hielt anlässlich der Hauptverhandlung vor Bezirksgericht vom 20. Oktober 2009 fest, er halte an seinen Anträgen gemäss Klage vom 25. Juni 2009 fest und stelle "folgenden präzisierenden Antrag": "Ziff. 3.5 des Scheidungsurteils (...) sei aufzuheben und neu wie folgt zu fassen: Der Kläger wird verpflichtet, jeweils im Voraus und auf den 1. eines jeden Monats an den Unterhalt seiner drei Kinder die allfällig bezogenen Kinderzulagen zu bezahlen, zahlbar bis zum ordentlichen Abschluss einer angemessenen Erstausbildung beziehungsweise bis zur Mündigkeit, falls eine Ausbildung vorher abgeschlossen wird". Das Bezirksgericht ging deshalb in seinem Urteil davon aus, der Beschwerdeführer verlange eine vollumfängliche Aufhebung seiner Kinderunterhaltspflicht (Ziff. 2 S. 3 des bezirksgerichtlichen Urteils; <ref-law>).
In seiner Berufungseingabe an das Obergericht hat der Beschwerdeführer ausgeführt, das Bezirksgericht habe seine Begehren in der Klage vom 25. Juni 2009, wonach die im Scheidungsurteil festgesetzten Unterhaltsbeiträge "angemessen abzuändern" seien, zu Unrecht dahingehend ausgelegt, er verlange eine vollumfängliche Aufhebung ("Abänderung auf Null") seiner Unterhaltspflicht. Dies stimme so nicht und er habe sich auch nie so geäussert (Ziff. 2 S. 6 der Berufungseingabe).
4.2.3 Aus seiner Berufungsbegründung geht damit klar und zweifelsfrei hervor, dass der Beschwerdeführer vor Obergericht nur eine Reduktion, nicht aber eine vollumfängliche Aufhebung ("Abänderung auf Null") der Kinderunterhaltsbeiträge verlangte. Damit blieb für eine Auslegung der Begehren des Beschwerdeführers im nun behaupteten Sinn (vollumfängliche Aufhebung, das heisst "Abänderung auf Null") von vornherein kein Raum. Abgesehen davon legt der Beschwerdeführer auch nicht dar (<ref-law>), aus welchen Erwägungen seiner Berufungsbegründung "mehr als deutlich" hervorgehen soll, dass er eine vollumfängliche Aufhebung seiner Unterhaltspflicht verlangt hat.
4.2.4 Blieb damit für das Obergericht für eine Auslegung der Berufungsanträge im Sinne einer vollumfänglichen Aufhebung der Unterhaltspflicht kein Raum, behauptet sodann der Beschwerdeführer zu Recht nicht, aus seiner Berufungsbegründung sei immerhin ersichtlich, auf welchen Betrag seine Unterhaltspflicht gegenüber den Kindern zu reduzieren sei.
4.2.5 Damit ist es nicht zu beanstanden, wenn das Obergericht von unbestimmten und unbezifferten Berufungsanträgen ausgegangen ist.
4.2.5 Damit ist es nicht zu beanstanden, wenn das Obergericht von unbestimmten und unbezifferten Berufungsanträgen ausgegangen ist.
4.3 4.3.1 Soweit der Beschwerdeführer auf die Streitwertberechnung der kantonalen Instanzen verweist (vgl. E. 3.2 oben), ändert dies am Ergebnis nichts, worauf nachfolgend einzugehen ist. Worin im Übrigen in diesem Zusammenhang eine Verletzung von <ref-law> über die Streitwertberechnung liegen soll, ist weder ersichtlich noch begründet dies der Beschwerdeführer (<ref-law>). Darauf ist von vornherein nicht einzutreten.
4.3.2 Die bezirksgerichtliche Streitwertberechnung ist für die Berufungsanträge vor Obergericht von vornherein nicht massgebend, da das Bezirksgericht - anders als der vor Bundesgericht einzig angefochtene Entscheid des Obergerichts (<ref-law>) - wie erwähnt (vgl. E. 4.2.2 oben) zum Ergebnis gelangte, der Beschwerdeführer verlange eine vollumfängliche Aufhebung seiner Unterhaltspflicht.
4.3.3 Im obergerichtlichen Entscheid findet sich der vom Beschwerdeführer erwähnte Streitwert einzig an einer Stelle, nämlich in der Rechtsmittelbelehrung.
Das Obergericht war verpflichtet, in der Rechtsmittelbelehrung einen Streitwert für die Beschwerde an das Bundesgericht anzugeben (<ref-law>). Konnte es diesen mangels bestimmten Berufungsanträgen (selbst mittels Auslegung der Begründung) nicht festsetzen, ist es nicht zu beanstanden, wenn es in der Rechtsmittelbelehrung und demnach einzig mit Blick auf das Erreichen der Streitwertgrenze für die Beschwerde in Zivilsachen zugunsten des Beschwerdeführers vom höchstmöglichen Streitwert ausgegangen ist. Daraus kann der Beschwerdeführer für die vorliegende Frage der mangelhaften Berufungsanträge nichts für sich ableiten.
5. 5.1 Schliesslich bringt der Beschwerdeführer vor, das Obergericht habe <ref-law> verletzt, weil es ihm nicht Gelegenheit gegeben habe, seine Anträge klarzustellen und zu ergänzen, sondern ohne Ansetzung einer Nachfrist nicht auf die Berufung eingetreten ist. Dies umso mehr, als es nach altem Recht (§ 61 Abs. 2 der Zivilprozessordnung des Kantons Zürich vom 13. Juni 1976 [ZPO/ZH; in Kraft bis 31. Dezember 2010]) üblich gewesen sei, dass das Gericht die klagende Partei auf das Bezifferungserfordernis aufmerksam gemacht habe.
5.2 Abgesehen davon, dass es vergebens ist, wenn der Beschwerdeführer altrechtliche kantonale Bestimmungen anruft oder auf eine frühere mildere kantonale Praxis verweist (<ref-ruling> E. 4.4.1 S. 377), wenn das Berufungsverfahren vor dem Obergericht der Schweizerischen Zivilprozessordnung unterstand (<ref-ruling> E. 2 S. 131 f.), betraf der von ihm angeführte <ref-law>/ZH das erstinstanzliche Verfahren. Für das altrechtliche Berufungsverfahren sah demgegenüber <ref-law>/ZH unter Androhung der Nichteintretensfolge vor, dass bezifferte Anträge zu stellen waren (vgl. dazu Urteil 5A_105/2012 vom 9. März 2012 E. 3.2, in: FamPra.ch 2012 S. 811; FRANK/STRÄULI/MESSMER, Kommentar zur zürcherischen Zivilprozessordnung, 3. Aufl. 1997, N. 29 zu <ref-law>/ZH und N. 2a ff. zu <ref-law>/ZH).
5.3 Gemäss <ref-law> gibt das Gericht einer Partei durch entsprechende Fragen Gelegenheit zur Klarstellung und Ergänzung, wenn ihr Vorbringen unklar, widersprüchlich, unbestimmt oder offensichtlich unvollständig ist.
5.4 Es kann offenbleiben, ob <ref-law> überhaupt auf mangelhafte Berufungsanträge Anwendung findet. So oder anders ist es ohnehin nicht Sache des Gerichts, prozessuale Nachlässigkeiten der Parteien auszugleichen (Urteile 5A_115/2012 vom 20. April 2012 E. 4.5.2; 4A_169/2011 vom 19. Juli 2011 E. 5.4).
Dem im ganzen kantonalen Verfahren anwaltlich vertretenen (vgl. dazu Urteile 5A_538/2011 vom 5. Juni 2012 E. 5.1; 4A_169/2011 vom 19. Juli 2011 E. 5.4) Beschwerdeführer war bei Einreichung seiner Berufungseingabe durchaus bewusst, dass seine Rechtsbegehren unklar waren, hat er dies doch im Zusammenhang mit der bezirksgerichtlichen Auslegung seiner Klagebegehren in der Berufungseingabe selbst thematisiert (vgl. E. 4.2.2 oben). Stellte er trotzdem und damit bewusst unbezifferte Berufungsanträge, ist es nicht Aufgabe des Gerichts, solche prozessuale Nachlässigkeiten auszugleichen.
6. Das Obergericht hat demnach kein Bundesrecht verletzt, wenn es auf den unbestimmten und unbezifferten Hauptberufungsantrag des Beschwerdeführers nicht eingetreten ist. Der Beschwerdeführer behauptet sodann zu Recht nicht, das Obergericht hätte bei unzulässigem Hauptberufungsantrag auf sein Eventualbegehren (Rückweisungsantrag) eintreten müssen, da aus der Berufungseingabe nicht hervorgeht, dass einer der Gründe von <ref-law> vorgelegen hätte.
7. 7.1 Das Obergericht hat das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung für das Berufungsverfahren wegen Aussichtslosigkeit (<ref-law>) der Berufung abgewiesen.
7.2 Der Beschwerdeführer macht vor Bundesgericht geltend, das Obergericht habe sein Gesuch "in materieller Hinsicht" nicht geprüft, da es auf die Berufung nicht eingetreten sei und daher davon ausgegangen sei, die Berufung sei aussichtslos. Er folgert deshalb, beim beantragten Ausgang des vorliegenden bundesgerichtlichen Verfahrens sei ihm auch vor Obergericht die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
7.3 Der Beschwerdeführer scheint zu verkennen, dass es sich bei der fehlenden Aussichtslosigkeit der Begehren (<ref-law>) um eine materielle Voraussetzung der unentgeltlichen Rechtspflege handelt, die das Obergericht geprüft, verneint und folglich das Gesuch abgewiesen hat.
Fehlt es der Berufung (auch unter Bezugnahme auf deren Begründung) entgegen der amtlich publizierten Praxis des Bundesgerichts an bezifferten Anträgen, durfte das Obergericht von der Aussichtslosigkeit der Berufung ausgehen (für den analogen Fall auf Ebene des Bundesgerichts vgl. Urteil 5A_669/2007 vom 4. August 2008 E. 2).
Eine Verletzung von Bundesrecht ist demnach auch insoweit nicht ersichtlich.
8. Aus den dargelegten Gründen muss die Beschwerde abgewiesen werden, soweit darauf einzutreten ist. Der Beschwerdeführer wird kostenpflichtig (<ref-law>). Der Beschwerdegegnerin ist kein entschädigungspflichtiger Aufwand entstanden (Art. 68 Abs. 1 und 2 BGG). Dem Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung für das bundesgerichtliche Verfahren kann nicht entsprochen werden, verdeutlichen doch die vorstehenden Erwägungen, dass die gestellten Begehren von Beginn an keinen Erfolg haben konnten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung für das bundesgerichtliche Verfahren wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 13. Februar 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Bettler