Sachverhalt:
A. Mit Vertrag vom 20. März 1996 mietete X._ (Mieter) von A Y._ (Vermieter) per 1. Mai 1996 eine 3-Zimmer-Wohnung in der Liegenschaft Z._strasse in 8038 Zürich.
Im Jahre 2001 klagte der Mieter beim Mietgericht Zürich gegen den Vermieter auf Zahlung von Fr. 9'000.-- sowie Herabsetzung des Mietzinses um Fr. 132.-- pro Monat vom 1. April 2002 bis zur Mängelbehebung. Als Mangel führte der Mieter Nachtruhestörungen durch die Mieterin B Y._ an. Während des Verfahrens reduzierte der Mieter seine Forderung auf Fr. 8'152.--. Mit Urteil vom 18. Juni 2002 wies das Mietgericht die Klage ab. Mit Beschluss vom 8. November 2002 hiess das Obergericht eine Berufung, mit welcher der Mieter die Zahlung von Fr. 2'500.-- verlangte, im Umfang von Fr. 2'000.-- gut.
Mit Schreiben vom 20. Dezember 2002 an den Anwalt des Vermieters teilte der Mieter mit, die Nachtruhestörungen durch B Y._ dauerten an, weshalb er bezüglich der künftigen Mietzinse jeweils Fr. 37.-- verrechnen werde. Vorbehältlich der Rechtskraft des Obergerichtsurteils werde er ebenfalls den Betrag von Fr. 2'000.-- verrechnen. Zudem verlangte der Mieter gestützt auf die Hypothekarzinssenkung der Zürcher Kantonalbank eine Mietzinssenkung von 5.66 %.
Nach dem Tod des Vermieters ging das Mietverhältnis auf seine Ehefrau C Y._ (nachstehend: Vermieterin) über.
Mit Schreiben vom 13. Januar 2003 teilte der Hauseigentümerverband Zürich (nachstehend: Liegenschaftsverwaltung) dem Mieter mit, der bisherige Nettomietzins von Fr. 863.-- werde ab dem 1. April 2003 zufolge Hypothekarzinssenkung um 5.66 % gesenkt und zufolge des Teuerungsausgleichs um 0.01 % und zufolge Kostensteigerungen vom September 2001 bis September 2002 um 1 % erhöht.
Im Schreiben vom 15. Januar 2003 erklärte die Liegenschaftsverwaltung gegenüber dem Mieter, ihm werde vorbehältlich der Rechtskraft des Obergerichtsurteils Fr. 2000.-- zugesprochen, er werde gebeten, ein Konto für die Überweisung dieses Betrages bekannt zu geben und für die Wohnung den ganzen Monatszins zu bezahlen.
Der Mieter antwortete mit Schreiben vom 28. Januar 2003, er werde wunschgemäss den vollen Monatsmietzins Februar 2003 überweisen. Der Betrag von Fr. 2'481.-- (Fr. 2'000.-- + [13 x Fr. 37.--] Januar 2002 bis Januar 2003) solle auf sein Postcheckkonto überwiesen werden, ebenso das jeweilige Monatsbetreffnis von Fr. 37.-- auf jedes Monatsende.
Am 23. Juni 2003 gab der Mieter unter Bezug auf sein Schreiben vom 20. Dezember 2002 gegenüber dem Rechtsanwalt der Vermieterin bekannt, er werde auf Zusehen hin mit der Geltendmachung seiner Forderung zuwarten, bis sich die finanzielle Situation der Vermieterin erholt habe. Er verzichte jedoch weder auf die Forderung, noch auf sein Verrechnungsrecht. Der Rechtsanwalt der Vermieterin bedankte sich für das Entgegenkommen des Mieters und gab an, er werde ihn nach Rücksprache mit seiner Klientschaft über das weitere Vorgehen orientieren.
Den Mietern der Liegenschaft Z._strasse teilte die Liegenschaftsverwaltung mit Schreiben vom 9. Februar 2004 mit, sie werde monatlich Fr. 8.-- als Pauschale für das Waschen berechnen, da Frau B Y._ seit einiger Zeit kein Geld mehr für die Waschmaschinenbenützung eingezogen habe. Nachdem der Mieter gegen diese Erhebung einer Pauschale Bedenken angemeldet hatte, erklärte die Liegenschaftsverwaltung mit Schreiben vom 26. Mai 2004, die Hauseigentümerschaft verzichte vorläufig auf ein Waschgeld.
Mit Schreiben vom 28. Juni 2005 ersuchte der Mieter die Vermieterin um eine Mietzinssenkung infolge der Hypothekarzinssenkung durch die Zürcher Kantonalbank und brachte vor, die Stadt Zürich habe substantielle Gebührensenkungen vorgenommen, weshalb die Anwendung der gewohnten, pauschalen "Kostensteigerungen" von 1 % pro Jahr nicht statthaft sei. Die Vermieterin setzte daraufhin mit amtlichem Formular vom 26. Juli 2005 den Nettomietzins von Fr. 825.-- entsprechend dem gesunkenen Hypothekarzinssatz um 5.66 % herab, verlangte jedoch eine Erhöhung von 1.12 % für den Teuerungsausgleich und von 2.75 % für Kostensteigerung von September 2002 bis Juni 2005, womit sie weiterhin von einer Kostensteigerung von 1 % pro Jahr ausging.
Mit amtlichem Formular vom 27. Dezember 2005 kündigte die Vermieterin das Mietverhältnis auf den 31. März 2006. Sie begründete die Kündigung damit, dass eine Nichte die Wohnung benötige.
Mit Eingabe vom 27. Januar 2006 focht der Mieter die Kündigung bei der Schlichtungsbehörde des Bezirkes Zürich an, welche nach erfolgloser Schlichtungsverhandlung am 24. März 2006 die Gültigkeit der Kündigung feststellte und das Mietverhältnis einmalig und definitiv bis zum 30. September 2007 erstreckte.
B. Am 20. März 2006 klagte der Mieter (Kläger) beim Mietgericht des Bezirkes Zürich gegen die Vermieterin (Beklagte) auf Ungültigerklärung der Kündigung. Mit Urteil vom 23. August 2007 wies das Mietgericht die Klage ab, erklärte die Kündigung für gültig und erstreckte das Mietverhältnis einmalig und definitiv um zwei Jahre bis zum 31. März 2008.
Eine gegen dieses Urteil gerichtete Berufung des Klägers wies das Obergericht des Kantons Zürich mit Beschluss vom 25. Januar 2008 ab, soweit es darauf eintrat.
Mit Zirkulationsbeschluss vom 24. Dezember 2008 hiess das Kassationsgericht des Kantons Zürich eine Nichtigkeitsbeschwerde des Klägers gut und hob den Beschluss des Obergerichts vom 25. Januar 2008 mit der Begründung auf, das Obergericht habe den Antrag des Klägers auf Rückweisung des Verfahrens an die Schlichtungsbehörde wegen fehlender persönlichen Anwesenheit der Vermieterin an der Schlichtungsverhandlung gestützt auf einen unzutreffenden Grund abgewiesen.
Mit Beschluss vom 25. Februar 2009 wies das Obergericht die Berufung des Klägers erneut ab, soweit es darauf eintrat.
Am 25. März 2009 fragte der Kläger das Obergericht schriftlich an, ob dessen Mitglieder zur Beklagten, ihrem Rechtsvertreter, zum Mietgerichtspräsidenten, zu den Mietrichtern und zur Schlichtungsvorsitzenden etc. familiäre, freundschaftliche oder wirtschaftliche Beziehungen hätten.
Mit Beschluss vom 16. September 2009 hiess das Kassationsgericht eine Nichtigkeitsbeschwerde des Klägers gegen den Beschluss des Obergerichts vom 25. Februar 2009 insoweit gut, als es darin eine Begründungsvariante strich. Im Übrigen wies das Kassationsgericht die Beschwerde ab, soweit es darauf eintrat.
C. Der Kläger (Beschwerdeführer) erhebt Beschwerde in Zivilsachen mit den Hauptanträgen, die Kündigung sei für nichtig bzw. ungültig zu befinden und aufzuheben, es seien Ziff. 1 Abs. 2 und 3, Ziff. 2, Ziff. 3 im Umfang von 3⁄4 der Kosten sowie Ziff. 4 des Zirkulationsbeschusses des Kassationsgerichts vom 16. September 2009 aufzuheben und dieser Beschluss sowie der Zirkulationsbeschluss des Kassationsgerichts vom 24. Dezember 2008 zur Behebung von Mängeln an die Vorinstanz zurückzuweisen.
Weiter stellt der Beschwerdeführer unter anderem die Eventualanträge, der Beschluss des Obergerichts vom 25. Februar 2009 sei aufzuheben, soweit die Kosten dem Beschwerdeführer auferlegt wurden; das Obergericht sei anzuweisen, diesen Beschluss neu zu eröffnen und das Schreiben des Beschwerdeführers vom 25. März 2009 betreffend Befangenheit zu beantworten.
Der Kläger ersucht zudem darum, ihm die unentgeltliche Prozessführung zu gewähren und der Beschwerde die aufschiebende Wirkung zu erteilen.
Die Beklagte (Beschwerdegegnerin) stellt bezüglich des Gesuchs um aufschiebende Wirkung kein Begehren, beantragt jedoch in ihrer Vernehmlassung, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne. Das Obergericht verzichtet darauf, sich zur Beschwerde und dem Gesuch um aufschiebende Wirkung vernehmen zu lassen.
Mit seiner unaufgefordert eingereichten Replik stellt der Beschwerdeführer die Anträge, es sei der Vertreter der Beschwerdegegnerin gemäss <ref-law> disziplinarisch zu massregeln und gemäss <ref-law> der zürcherischen Aufsichtsbehörde Meldung wegen Verletzung von Art. 8 Abs. 1 und Art. 12 lit. a BGFA zu erstatten. Eventuell sei die Vernehmlassung als unzulässig im Sinne von <ref-law> aus dem Recht zu weisen oder als ungebührlich im Sinne von <ref-law> an die Beschwerdegegnerin zurückzuweisen.

Erwägungen:
1. Die Vernehmlassung der Beschwerdegegnerin verletzt weder den Anstand im Sinne von <ref-law> noch ist sie ungebührlich im Sinne von <ref-law>, weshalb keine entsprechenden Sanktionen zu ergreifen sind. Inwiefern Art. 8 Abs. 1 oder Art. 12 lit. a des Bundesgesetzes über die Freizügigkeit der Anwältinnen und Anwälte (BGFA; SR 935.61) verletzt sein sollen, legt der Beschwerdeführer nicht dar und ist auch nicht ersichtlich. Demnach hat keine Meldung nach <ref-law> zu erfolgen.
2. 2.1 Gegenstand des Verfahrens bildet eine Zivilsache (<ref-law>). Die Rechtsbegehren des Beschwerdeführers sind im kantonalen Verfahren nicht vollständig geschützt worden (<ref-law>), der massgebende Streitwert beträgt mehr als Fr. 15'000.-- (<ref-law>) und die Beschwerdefrist ist eingehalten (Art. 100 Abs. 1 und 6 BGG i.V.m. Art. 44 f. BGG).
2.2 Weiter setzt die Beschwerde in Zivilsachen voraus, dass das angefochtene Urteil letztinstanzlich ist (<ref-law>). Die Beschlüsse des Obergerichts konnten mit kantonaler Nichtigkeitsbeschwerde nach <ref-law>/ZH beim Kassationsgericht des Kantons Zürich angefochten werden, was der Beschwerdeführer auch tat. Die Beschlüsse des Obergerichts sind daher insoweit nicht kantonal letztinstanzlich, als sie vom Kassationsgericht hätten überprüft werden können.
Nach § 285 Abs. 1 und 2 ZPO/ZH ist die Nichtigkeitsbeschwerde grundsätzlich ausgeschlossen, wenn das Bundesgericht frei überprüfen kann, ob der geltend gemachte Mangel vorliegt. Die Nichtigkeitsbeschwerde ist stets zulässig, wenn eine Verletzung von Art. 8, 9, 29 oder 30 der Bundesverfassung oder von Art. 6 EMRK geltend gemacht wird. Als Verletzung des Willkürverbots gemäss <ref-law> kann das Kassationsgericht die Rüge der willkürlichen Sachverhaltsfeststellung prüfen. Da das BGG - anders als das Bundesgesetz über die Organisation der Bundesrechtspflege vom 16. Dezember 1943 (OG) - keine spezielle Rüge des offensichtlichen Versehens vorsieht, kann diese Rüge als Unterfall der Rüge der willkürlichen Sachverhaltsfeststellung gemäss <ref-law> mit der Nichtigkeitsbeschwerde erhoben werden (Beschluss des Kassationsgerichts vom 6. März 2008, publ. in: ZR 107/2008, Nr. 21 S. 65 ff., 76).
2.3 Der Beschwerdeführer macht geltend, das Kassationsgericht habe Versehensrügen unter der Geltung des OG nicht zugelassen. Die entsprechende Praxisänderung des Kassationsgerichts vom 6. März 2008 könne ihm nicht entgegengehalten werden, weil sie erst nach der Einreichung seiner (ersten) Nichtigkeitsbeschwerde veröffentlicht worden sei. Der Entscheid des Obergerichts sei ihm deshalb neu zu eröffnen, damit er gemäss neuer Praxis vor Kassationsgericht auch Versehensrügen vorbringen könne, oder es seien diese vom Bundesgericht zu prüfen.
2.4 Der Beschwerdeführer übersieht, dass das Kassationsgericht mit dem Beschluss vom 6. März 2008 lediglich seine Rechtsprechung unter der Geltung des OG an das BGG angepasst hat. Diese Anpassung war für den Beschwerdeführer vorhersehbar, da das Bundesgericht bereits im Jahr 2007 klarstellte, dass unter einer offensichtlich unrichtigen Sachverhaltsfeststellung nach Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG eine willkürliche und nicht bloss eine offensichtlich auf Versehen beruhende Sachverhaltsfeststellung gemäss Art. 55 Abs. 1 lit. d und 63 Abs. 3 OG zu verstehen ist (<ref-ruling> E. 1.2.2; vgl. auch Urteil 4A_21/2007 vom 22. Juni 2007 E. 6.1). Damit erübrigt sich eine neue Eröffnung des ersten Beschlusses des Obergerichts. Zudem ist auf die nicht bereits vor Kassationsgericht erhobenen Rügen willkürlicher bzw. offensichtlich versehentlicher Sachverhaltsfeststellungen mangels Letztinstanzlichkeit nicht einzutreten. Gleiches gilt für die direkt gegen die Beschlüsse des Obergerichts erhobenen Rügen der Verletzung des rechtlichen Gehörs gemäss <ref-law> und von Art. 6 EMRK. Unzulässig ist somit namentlich die Rüge, das Obergericht habe das rechtliche Gehör verletzt, indem es nicht auf den Einwand eingegangen sei, die Beschwerdegegnerin habe dem Beschwerdeführer gekündigt, weil sie irrtümlich angenommen habe, er sei der Mieter einer Dreizimmerwohnung mit der kürzesten Mietdauer.
2.5 Dagegen ist die Letztinstanzlichkeit der Beschlüsse des Obergerichts bezüglich der Rügen der Verletzung von Bundeszivilrecht zu bejahen, weil insoweit die Nichtigkeitsbeschwerde ausgeschlossen ist (vgl. Urteil 4A_398/2008 vom 18. Dezember 2008 E. 1.2.2).
3. 3.1 In der kantonalen Berufung beantragte der Beschwerdeführer, es sei festzustellen, dass die Beschwerdegegnerin infolge selbst verschuldeten Irrtums nach Beendigung des Mietverhältnisses gemäss <ref-law> zu Schadenersatz verpflichtet sei. Das Obergericht trat auf diesen Antrag nicht ein, weil er erstmals im Berufungsverfahren gestellt worden und damit unzulässig sei. Das Kassationsgericht verneinte in seinem Beschluss vom 24. Dezember 2008 in Erwägung 3 (S. 4) insoweit eine Verletzung kantonalen Rechts.
3.2 Vor Bundesgericht bringt der Beschwerdeführer sinngemäss vor, sowohl das Ober- wie das Kassationsgericht seien auf seine Ausführungen zur irrtümlichen Kündigung mangels eines förmlichen Antrags nicht eingetreten. Dies verletze das Verbot des überspitzten Formalismus, zumal ein Antrag sich auch aus der Begründung der Rechtsschrift ergebe könne. Weiter hätten sich die Irrtümer der Beschwerdegegnerin erst anlässlich des Verfahrens vor Mietgericht ereignet, sodass ein entsprechender früherer Antrag nicht möglich gewesen sei. Er halte daher am Feststellungsantrag fest.
3.3 Überspitzter Formalismus als besondere Form der Rechtsverweigerung liegt insbesondere vor, wenn eine Behörde formelle Vorschriften mit übertriebener Schärfe handhabt oder an Rechtsschriften überspannte Anforderungen stellt und damit dem Bürger den Rechtsweg in unzulässiger Weise versperrt (<ref-ruling> E. 2a S. 6 mit Hinweisen). Nicht jede prozessuale Formstrenge stellt jedoch einen überspitzten Formalismus dar, sondern nur jene, die durch kein schutzwürdiges Interesse mehr gerechtfertigt ist und zum blossen Selbstzweck wird. Prozessuale Formen sind unerlässlich, um die ordnungsgemässe Abwicklung des Verfahrens zu gewährleisten. Eingaben an Behörden, vor allem Rechtsmittelschriften, haben daher im Allgemeinen bestimmten formellen Anforderungen zu genügen (<ref-ruling> E. 2.4.2 S. 248 mit Hinweisen).
3.4 Da der Beschwerdeführer nach seiner Darstellung die von ihm geltend gemachten Irrtümer der Beschwerdegegnerin bereits im erstinstanzlichen Verfahren erkannt hatte, ist nicht ersichtlich, weshalb es ihm unmöglich oder unzumutbar gewesen sein soll, in diesem Verfahren einen entsprechenden Antrag zu stellen. Inwiefern sich ein solcher aus der Begründung der Klage ergeben soll, legt der Beschwerdeführer nicht dar. Demnach ist insoweit eine Verletzung des Verbots des überspitzten Formalismus zu verneinen. Damit erweist sich das vor Bundesgericht gestellte Begehren, es sei festzustellen, dass die Kündigung irrtümlich erfolgte und die Beschwerdegegnerin für sämtliche daraus resultierende Kosten und Schäden aufzukommen habe, als neu und unzulässig (<ref-law>). Dasselbe gilt bezüglich des Eventualbegehrens auf Sicherstellung dieser Schadenersatzforderung.
4. 4.1 Der Beschwerdeführer macht geltend, das Obergericht habe nach Erhalt des Rückweisungsbeschlusses des Kassationsgerichts vom 24. Dezember 2008 mit dessen Umsetzung die 30-tägige Frist zur Erhebung einer Beschwerde beim Bundesgericht abwarten müssen. Der Beschluss vom 25. Februar 2009 sei vor Ablauf dieser Frist ergangen, weshalb er von Bundesrechts wegen nichtig oder anfechtbar sei.
4.2 Der Beschwerdeführer legt jedoch nicht dar und es ist auch nicht ersichtlich, inwiefern die Voraussetzungen der direkten Anfechtung des Zwischenentscheids vom 24. Dezember 2008 gemäss <ref-law> vorgelegen haben sollen, weshalb kein Anlass bestand, die Rechtsmittelfrist abzuwarten. Damit hat das Obergericht entgegen der Annahme des Beschwerdeführers auch nicht den Anschein der Befangenheit erweckt, indem es relativ rasch nach Erhalt des Rückweisungsentscheides neu entschieden hat.
5. 5.1 In seinem ersten Beschluss vom 24. Dezember 2008 führte das Kassationsgericht in Erwägung II.9 auf Seite 11 aus, mit der Aufhebung des angefochtenen Beschlusses [des Obergerichts] sei es möglich, dass das ganze Verfahren an die Schlichtungsbehörde zurückgewiesen werde. Damit würden die weiteren, auf den bisherigen Verfahren beruhenden Rügen obsolet. Sie seien deshalb nicht zu prüfen.
5.2 Nachdem das Obergericht in seinem Beschluss vom 25. Februar 2009 auf eine Rückweisung an die Schlichtungsbehörde verzichtet hatte, beantragte der Beschwerdeführer in seiner zweiten Nichtigkeitsbeschwerde: "Eventualiter seien die verbleibenden Nichtigkeitsgründe der Nichtigkeitsbeschwerde vom 13. März 2008 gemäss den Erwägungen der Ziff. 9 des Zirkulationsbeschlusses vom 24. Dezember 2008 zu prüfen."
5.3 Auf diesen Eventualantrag trat das Kassationsgericht in seinem Beschluss vom 16. September 2009 mit der Begründung nicht ein, dass die blosse Verweisung auf frühere Vorbringen den Begründungsanforderungen nicht genügten. Aus Erwägung II.9 des Beschlusses vom 24. Dezember 2008 folge nicht, dass die in diesem Verfahren als obsolet qualifizierten Rügen im Falle der unterlassenen Rückweisung an die Schlichtungsbehörde in einem späteren Beschwerdeverfahren geprüft würden, ohne dass sie in der neuen Nichtigkeitsbeschwerde aufgeführt würden (E. 11 S. 17 f.).
5.4 Der Beschwerdeführer rügt, diese Erwägung verstosse gegen Treu und Glauben, da Erwägung II.9 des ersten Kassationsbeschlusses suggeriere, dass die nicht behandelten Rügen geprüft würden, soweit sie sich nachträglich nicht als obsolet erweisen. Zu verlangen, dass diese Rügen nochmals in der neuen Beschwerde wiedergegeben würden, erschwere - auch wenn die copy and paste Taste zur Verfügung stehe - die Verfolgung materieller Ansprüche übermässig und sei damit überspitzt formalistisch.
5.5 Entgegen der Annahme des Beschwerdeführers ergibt sich aus Erwägung II.9 des ersten Beschlusses des Kassationsgerichts nicht, dass die damals als obsolet betrachteten Rügen in einem späteren Verfahren geprüft würden, auch wenn sie darin nicht prozesskonform vorgebracht werden. Dem Beschwerdeführer war durchaus zuzumuten, die Rügen, deren Prüfung er weiterhin verlangt, in der zweiten Nichtigkeitsbeschwerde wiederzugeben. Es ist jedoch nicht Sache des Kassationsgerichts die Akten nach jenen Rügen zu durchforsten, an denen der Beschwerdeführer festhalten will. Demnach ist insoweit ein überspitzter Formalismus und damit auch die vom Beschwerdeführer daraus abgeleitete Verletzung des rechtlichen Gehörs zu verneinen.
6. In seiner zweiten Nichtigkeitsbeschwerde hatte der Beschwerdeführer geltend gemacht, das Obergericht habe durch sein parteiisches prozessuales Vorgehen den Anschein der Befangenheit erweckt. Das Kassationsgericht kam zum Ergebnis, die Rüge sei unbegründet (E. 12 S. 19).
Der Beschwerdeführer setzt sich mit dieser Erwägung in seiner Beschwerde nicht auseinander. Auf seine die behauptete Befangenheit betreffenden Ausführungen in der Replik kann nicht eingetreten werden, weil eine Ergänzung der Beschwerdeschrift im vorliegenden Verfahren unzulässig ist (vgl. <ref-law>). Sodann legt der Beschwerdeführer nicht dar, weshalb das Obergericht von Bundesrechts wegen verpflichtet gewesen sein soll, auf die im Schreiben vom 25. März 2009 nach Abschluss des obergerichtlichen Verfahrens zur Unabhängigkeit der Oberrichter gestellten allgemeinen Fragen zu antworten. Das Obergericht ist daher nicht dazu anzuhalten.
7. 7.1 Die schriftliche Kündigung eines Mietverhältnisses entfaltet nach den allgemeinen Grundsätzen über den Zugang empfangsbedürftiger Willenserklärungen ihre Wirkung, sobald sie in den Machtbereich des Adressaten gelangt, auch wenn er davon tatsächlich keine Kenntnis nimmt (<ref-ruling> E. 3a). Kann ein eingeschriebener Brief nicht zugestellt werden, gilt er im Allgemeinen an dem Tag als empfangen, an dem er erstmals auf der Post abgeholt werden kann (SVIT-Kommentar, 3. Aufl. 2008 N. 5a VorArt. 266-266o; WEBER, in: Basler Kommentar, OR I, 4. Aufl. 2007, N. 1a zu <ref-law>; vgl. auch Lachat und andere, Das Mietrecht für die Praxis, 8. Aufl. 2009, S. 519 Rz. 25/6.3).
7.2 Indem das Obergericht entsprechend dieser Rechtsprechung und Lehre annahm, bei Kündigungen gelte die uneingeschränkte Empfangstheorie, hat es entgegen der Meinung des Beschwerdeführers kein Bundesrecht verletzt.
8. 8.1 Gemäss <ref-law> ist die Kündigung durch den Vermieter anfechtbar, wenn sie vor Ablauf von drei Jahren nach Abschluss eines mit dem Mietverhältnis zusammenhängenden Schlichtungs- oder Gerichtsverfahrens ausgesprochen wird, indem der Vermieter: (1) zu einem erheblichen Teil unterlegen ist; (2) seine Forderung oder Klage zurückgezogen oder erheblich eingeschränkt hat; (3) auf die Anrufung des Richters verzichtet hat; (4) mit dem Mieter einen Vergleich geschlossen oder sich sonst wie geeinigt hat.
8.2 Das Obergericht ging davon aus, der Entscheid vom 8. November 2002 habe keine Sperrfrist gemäss Art. 271a Abs. 1 lit. e Ziff. 1 OR auslösen können, weil die Beschwerdegegnerin in diesem Verfahren, ausgehend vom ursprünglich eingeklagten Betrag, zu über 75 % obsiegt habe und damit nicht zu einem erheblichen Teil unterlegen sei.
8.3 Der Beschwerdeführer bringt vor, sowohl das Miet- wie das Obergericht hätten den Eventualstandpunkt der Beschwerdegegnerin, wonach das Urteil vom 8. November 2008 an diesem Tag in Rechtskraft erwachsen sei, zu Recht nicht in ihre Erwägungen einbezogen, da die Beschwerdegegnerin in ihrem Schreiben vom 15. Januar 2003 die Zahlung von Fr. 2000.-- lediglich vorbehältlich der Rechtskraft des Obergerichtsurteils zugesagt habe. Dieser Vorbehalt wäre bei einem rechtskräftigen Urteil nutzlos gewesen.
8.4 Die Sperrfrist gemäss Art. 271a Abs. 1 lit. e Ziff. 1 OR wegen Unterliegens in einem Schlichtungs- oder Gerichtsverfahren beginnt mit dem Abschluss des Verfahrens durch einen rechtskräftigen Entscheid (HIGI, in: Zürcher Kommentar, Bd. V2b, 4. Aufl. 1996, N. 250 und 268 zu <ref-law>; LACHAT UND ANDERE, a.a.O., S. 624 Rz. 29/5.5.5; WEBER, a.a.O., N. 24 zu Art. 271/271a OR). Urteile, welche mit keinem ordentlichen Rechtsmittel angefochten werden können, werden je nach kantonaler Prozessordnung mit der Ausfällung oder Zustellung rechtskräftig (VOGEL/SPÜHLER, Grundriss des Zivilprozessrechts, 8. Aufl. 2006, S. 226 Rz. 62). Die Zürcher Zivilprozessordnung vom 13. Juni 1976 stellt insoweit auf den Zeitpunkt der Fällung des Entscheids ab (<ref-law>/ZH). Der Beschluss vom 8. November 2002, der mit einem Streitwert von Fr. 2'500.-- mit keinem ordentlichen Rechtsmittel angefochten werden konnte, ist somit - unabhängig vom Schreiben der Beschwerdegegnerin vom 15. Januar 2003 - mit der Fällung rechtskräftig geworden. Hätte der Beschluss vom 8. November 2002 eine dreijährige Sperrfrist ausgelöst, wäre diese im Zeitpunkt der Kündigung vom 27. Dezember 2005 bereits abgelaufen gewesen. Damit ist nicht entscheiderheblich, ob eine solche Sperrfrist bestanden hat, weshalb auf die Kritik des Beschwerdeführers an der entsprechenden Erwägung des Obergerichts nicht einzutreten ist.
9. 9.1 Gemäss <ref-law> ist die Regelung der Anfechtbarkeit einer Vermieterkündigung gemäss <ref-law> (vgl. E. 8.1 hiervor) auch anwendbar, wenn der Mieter durch Schriftstücke nachweisen kann, dass er sich mit dem Vermieter ausserhalb eines Schlichtungs- oder Gerichtsverfahrens über eine Forderung aus dem Mietverhältnis geeinigt hat. Nach der Rechtsprechung gilt als Einigung im Sinne von <ref-law> nur eine einvernehmliche Streitbeilegung, mittels der eine unter den Parteien kontroverse Rechtsfrage abschliessend geklärt wird. Fälle, in denen es zu einer Auseinandersetzung gar nicht erst kommt, weil die eine oder andere Partei dem Begehren des Vertragspartners sogleich entspricht, werden daher nicht von <ref-law> erfasst (<ref-ruling> E. 2 mit Hinweisen).
9.2 Das Obergericht verneinte eine Einigung im Sinne von <ref-law> und nahm an, insoweit sei ohne Belang, ob die Beschwerdegegnerin ihrer Verpflichtung, gemäss dem Beschluss vom 8. November 2002 Fr. 2000.-- zu zahlen, sofort oder erst vier Monate später nachkam. Der Beschwerdeführer habe in seinem Schreiben vom 20. Dezember 2002 beantragt, der Mietzins sei wegen Nachtruhestörung um Fr. 37.-- und gestützt auf den gesunkenen Hypothekarzinssatz um 5.66 % herabzusetzen. Die Hypothekarzinssenkung sei umgehend gewährt worden. Bezüglich der Mietzinsherabsetzung um Fr. 37.-- sei es nicht zu einer Einigung gekommen. Die Beschwerdegegnerin habe sodann in ihrem Schreiben vom 26. Mai 2004 nur vorläufig auf die Erhebung eines Waschgeldes verzichtet und damit ihre diesbezügliche Forderung nicht ohne Weiteres fallen lassen, weshalb es auch in diesem Fall nicht zu einem Vergleich gekommen sei. Ein solcher sei auch nicht dadurch zustandegekommen, dass der Beschwerdeführer in seinem Herabsetzungsbegehren vom 28. Juni 2005 eine pauschale Gebührenerhöhung von 1 % als nicht statthaft erklärte und später - obwohl die Beschwerdegegnerin diese Pauschale weiterhin zur Anwendung brachte - dagegen nicht gerichtlich vorgegangen sei.
9.3 Der Beschwerdeführer macht sinngemäss geltend, nach dem Vertrauensprinzip habe sein Schreiben vom 23. Juni 2003 dahingehend verstanden werden müssen, dass er auf Zusehen hin auf die Geltendmachung der letzten verbleibenden strittigen Position, d.h. die aufgelaufenen Monatsbetreffnisse über Fr. 37.--, verzichtete. Dies habe die Beschwerdegegnerin dankend akzeptiert. Demnach seien die damals streitigen Forderungen aussergerichtlich beigelegt worden.
Der Beschwerdeführer lässt jedoch ausser Acht, dass er in seinem Schreiben vom 23. Juni 2003 bloss eine Stundung gewährte und ausdrücklich an seinen Forderungen festhielt, weshalb daraus nach dem Vertrauensprinzip nicht auf einen Forderungsverzicht geschlossen werden kann. Dasselbe gilt bezüglich des Schreibens der Beschwerdegegnerin, mit dem sie "vorläufig" auf ein Waschgeld verzichtete und damit zum Ausdruck brachte, dass insoweit keine abschliessende Einigung gefunden werden konnte. Das Obergericht hat somit nicht widersprüchlich argumentiert, wenn es insoweit eine Einigung gemäss <ref-law> verneinte. Dabei ist entgegen der Annahme der Beschwerdeführers ohne Bedeutung, ob er bei einer gerichtlichen Auseinandersetzung obsiegt hätte und ob insoweit eine Bagatelldifferenz vorliegt.
9.4 Alsdann macht der Beschwerdeführer dem Sinne nach geltend, die Beschwerdegegnerin habe seinen Forderungen auf eine Mietzinsherabsetzung von 5.66 % gestützt auf den gesunkenen Hypothekarzins zwar entsprochen, gleichzeitig jedoch den Mietzins zufolge Teuerung und Kostensteigerungen erhöht und damit konkludent eine Kompromiss- bzw. Gegenofferte unterbreitet, welche der Beschwerdeführer gemäss <ref-law> stillschweigend akzeptiert habe. Insoweit sei von einer Einigung im Sinne von Art. 271a Abs. 2 auszugehen.
9.5 Dieser Argumentaion kann nicht gefolgt werden. Zwischen der umgehend gewährten Mietzinsanpassung an den Hypothekarzinssatz und der Pauschale für Kostensteigerung besteht kein innerer Zusammenhang. Der Forderung des Beschwerdeführers auf eine Reduktion dieser Pauschale hat die Beschwerdegegnerin weder ganz noch teilweise entsprochen. Daher kann insoweit - selbst wenn der Beschwerdeführer dies akzeptierte - nicht von einem Vergleich gesprochen werden.
9.6 Weiter rügt der Beschwerdeführer, entgegen der Annahme des Obergerichts könne auch eine Vereinbarung über die Erfüllung einer bereits gerichtlich festgestellten Forderung eine Einigung gemäss <ref-law> darstellen. Diese Rüge ist unbegründet, weil nach der Rechtsprechung <ref-law> eine Einigung über eine strittige Forderung voraussetzt (vgl. E. 9.1 hiervor).
10.
10.1 Bei der Miete von Wohn- und Geschäftsräumen ist die Kündigung anfechtbar, wenn sie gegen den Grundsatz von Treu und Glauben verstösst (<ref-law>). Die Kündigung muss auf Verlangen begründet werden (<ref-law>). Allgemein gilt eine Kündigung als treuwidrig, wenn sie ohne objektives, ernsthaftes und schützenswertes Interesse ausgesprochen wird. Eine Kündigung verstösst namentlich gegen Treu und Glauben, wenn die angegebene Begründung offensichtlich bloss vorgeschoben ist (<ref-ruling> E. 4.1 S. 119). Bezüglich der Kündigung durch den Vermieter werden in <ref-law> beispielhaft Kündigungsgründe genannt, welche mit dem Grundsatz von Treu und Glauben nicht vereinbar sind. So ist gemäss <ref-law> eine Kündigung anfechtbar, wenn sie ausgesprochen wird, weil der Mieter nach Treu und Glauben Ansprüche aus dem Mietverhältnis geltend macht. Dagegen ist eine Kündigung zulässig, wenn damit dem Vermieter oder seinen nahen Verwandten ermöglicht werden soll, die Wohnung selbst zu benützen (Urteil 4C.411/2006 vom 9. Februar 2007 E. 2.1). Die Feststellung des Kündigungsgrundes bzw. -motivs betrifft eine Tatfrage (<ref-ruling> E. 2b S. 486; <ref-ruling> E. 3b S. 462).
Nach der Rechtsprechung des Bundesgerichts obliegt es dem Empfänger der Kündigung zu beweisen, dass diese aus einem verpönten oder ohne schützenswerten Grund erfolgte. Der Kündigende hat jedoch redlich zur Wahrheitsfindung beizutragen; er hat im Bestreitungsfall alle für die Beurteilung des angegebenen Kündigungsgrunds notwendigen Unterlagen vorzulegen (<ref-ruling> E. 4.1 S. 119, mit Hinweisen; vgl. auch Urteil 4A_345/2007 vom 8. Januar 2008 E. 2.4.3). In diesem Sinne hat der Kündigende den Kündigungsgrund zumindest glaubhaft zu machen (Urteil 4C.170/2004 vom 27. August 2004 E. 2.1, übersetzt publ. in: MRA 2004 S. 137; Urteil 4C.411/2006 vom 9. Februar 2007 E. 2.2, publ. in MRA 2/07 S. 45 ff., 49).
10.2 Das Obergericht kam mit dem Mietgericht zum Ergebnis, es sei glaubhaft, dass die Beschwerdegegnerin die Wohnung gekündigt habe, damit diese von ihrer Enkelin bewohnt werden kann. Dafür, dass die Beschwerdegegnerin gekündigt habe, weil der Beschwerdeführer nach Treu und Glauben Ansprüche aus dem Mietervertrag geltend gemacht habe, bestünden keine Anhaltspunkte.
10.3 Der Beschwerdeführer bringt vor, die Senkung des Beweismasses vom Regelbeweis auf das Glaubhaftmachen sei sachlich nicht zu rechtfertigen. Er setzt sich jedoch mit der vorgenannten Rechtsprechung des Bundesgerichts nicht auseinander (vgl. E. 10.1) und zeigt nicht auf, inwiefern sich eine Praxisänderung rechtfertigen soll, was auch nicht ersichtlich ist.
10.4 Soweit der Beschwerdeführer in diesem Zusammenhang eine willkürliche Beweiswürdigung oder die Verletzung kantonaler Beweisvorschriften rügt, ist mangels Ausschöpfung des Instanzenzugs darauf nicht einzutreten(vgl. E. 2.4 hiervor).
10.5 Alsdann führt der Beschwerdeführer dem Sinne nach aus, die Kündigung sei unnütz gewesen, weil mit einer Erstreckung von zwei bis drei Jahren hätte gerechnet werden müssen und daher zu erwarten gewesen sei, die Enkelin der Beschwerdegegnerin hätte ihr bereits seit vier Jahren betriebenes Studium vor Bezug der Wohnung bereits abgeschlossen.
Die Zulässigkeit der Kündigung ist jedoch im Zeitpunkt zu beurteilen, im dem sie ausgesprochen wird. Erst wenn von der Wirksamkeit der Kündigung auszugehen ist, kommt eine Erstreckung überhaupt in Frage. Diese Möglichkeit vermag daher bezüglich der Berechtigung zur Kündigung aus Eigenbedarf nichts zu ändern (Urteil 4C.333/1997 vom 8. Mai 1998 E. 3b). Soweit der Beschwerdeführer geltend macht, der angegebene Eigenbedarf sei nunmehr während des Prozesses weggefallen, bringt er eine neue Tatsachenbehauptung vor, welche nicht zu hören ist (<ref-law>).
10.6 Nach dem Gesagten verstösst die Annahme des Obergerichts, die Beschwerdegegnerin habe glaubhaft gemacht, wegen Eigenbedarfs gekündigt zu haben, nicht gegen Bundesrecht. Der Eventualbegründung, wonach die Kündigung selbst dann nicht missbräuchlich gewesen wäre, wenn sie zur Erzielung eines höheren Mietzinses ausgesprochen worden wäre, kommt daneben keine selbständige Bedeutung zu. Auf die gegen diese Eventualbegründung gerichtete Kritik des Beschwerdeführers ist daher nicht einzutreten.
11.
11.1 Der Mieter kann die Erstreckung des Mietverhältnisses verlangen, wenn die Beendigung der Miete für ihn oder seine Familie eine Härte zur Folge hätte, die durch die Interessen des Vermieters nicht zu rechtfertigen wäre (<ref-law>). Bei der Interessenabwägung berücksichtigt die zuständige Behörde insbesondere die Umstände des Vertragsschlusses und den Inhalt des Vertrages, die Dauer des Mietverhältnisses, die persönlichen, familiären und wirtschaftlichen Verhältnisse der Parteien und deren Verhalten, einen allfälligen Eigenbedarf des Vermieters für sich, nahe Verwandte oder Verschwägerte sowie die Dringlichkeit dieses Bedarfs und die Verhältnisse auf dem örtlichen Markt für Wohn- und Geschäftsräume (<ref-law>). Die Dauer der Erstreckung beträgt für Wohnräume höchstens vier Jahre, wobei im Rahmen der Höchstdauer eine oder zwei Erstreckungen gewährt werden können (<ref-law>). Die Frage, ob eine erstmalige oder definitive Erstreckung gewährt werden soll, ist gestützt auf eine Interessenabwägung im Einzelfall zu beantworten. Welche Erstreckungsart gewählt und wie die Erstreckung bemessen wird, ist eine Ermessensfrage (Urteile 4A_105/2009 vom 5. Juni 2009 E. 3.2; 4C.445/2008 vom 7. Juni 2007 E. 5.2.3, übersetzt publ. in: MRA 3/07 S. 90 ff., 93). Derartige Ermessensentscheide überprüft das Bundesgericht mit Zurückhaltung und greift nur ein, wenn die Vorinstanz grundlos von in Lehre und Rechtsprechung anerkannten Grundsätzen abgegangen ist, wenn sie Tatsachen berücksichtigt hat, die für den Entscheid im Einzelfall keine Rolle hätten spielen dürfen, oder wenn sie umgekehrt Umstände ausser Betracht gelassen hat, die hätten beachtet werden müssen. Es greift ausserdem in Ermessensentscheide ein, wenn sich diese als offensichtlich unbillig, als in stossender Weise ungerecht erweisen (<ref-ruling> E. 2 S. 123 f. mit Hinweisen).
11.2 Das Mietgericht erstreckte das Mietverhältnis in seinem Entscheid vom 23. August 2007 einmalig und definitiv um zwei Jahre. Zur Begründung führte es zusammengefasst aus, der Beschwerdeführer könne sich keinen Fr. 1'000.-- übersteigenden Mietzins pro Monat leisten und benötige für seine Familie mit zwei Kindern mindestens eine Dreizimmerwohnung. Aufgrund der Dauer des Mietverhältnisses bestehe keine Ortsgebundenheit. Eine solche ergebe sich auch nicht daraus, dass das älteste Kind den Kindergarten besuche oder eingeschult würde, zumal ein Kindergarten- oder Schulwechsel in einen anderen Stadtteil Zürichs oder in eine Aussengemeinde zumutbar sei. Jedoch dürfte das Finden einer geeigneten Wohnung schwierig sein, was härtebegründend zu berücksichtigen sei. Der Eigenbedarf der Enkelin der Beschwerdegegnerin sei nicht dringend, weshalb sich eine Erstreckung rechtfertige. Diese sei einmalig zu gewähren, weil der Beschwerdeführer ungenügende Suchbemühungen vorgenommen und er seine schwierige finanzielle Situation selbst zu vertreten habe, da er aus freien Stücken seit über fünf Jahren an einer Dissertation schreibe, obwohl es ihm zuzumuten wäre, eine Voll- oder Teilzeitstelle anzunehmen.
11.3 Das Obergericht bestätigte die vom Mietgericht vorgenommene Erstreckung und erwog, eine gewisse Quartierbezogenheit infolge der Mietdauer von beinahe zehn Jahren könne zwar nicht völlig verneint werden. Jedoch bestehe aus beruflichen Gründen keine Standortgebundenheit, da der Beschwerdeführer die universitären Einrichtungen auch von der Agglomeration aus erreichen könne. Er habe sodann zu Protokoll gegeben, dass er mit seiner Familie oft in Slowenien sei, weshalb schon deshalb keine Standortgebundenheit bestehe und auch der Grad der Quartierbezogenheit zu relativieren sei. Seinem ältesten Kind sei ein Kindergarten- resp. Schulwechsel zuzumuten, wenngleich zutreffen möge, dass stabile Verhältnisse optimaler wären. Der Beschwerdeführer habe jedoch durch die Aufnahme einer Erwerbstätigkeit selber für solche Verhältnisse zu sorgen, wobei auch seiner Ehefrau die Aufnahme mindestens einer Teilzeiterwerbstätigkeit zuzumuten sei. Das Mietgericht habe demnach zu Recht lediglich eine einmalige Erstreckung gewährt, weil der Kläger seine schwierige finanzielle Situation selber zu vertreten habe.
11.4 Der Beschwerdeführer bringt in diesem Zusammenhang neben unzulässiger Kritik an den vorinstanzlichen Sachverhaltsfeststellungen dem Sinne nach vor, das Obergericht habe seine Quartierverbundenheit nicht dadurch relativieren dürfen, dass er die Einrichtungen der Universität auch von der Agglomeration aus habe erreichen können, weil damit der längere Arbeitsweg und der Verlust des angestammten Quartiers für ihn und seine Familie ausser Acht gelassen würde. Dass diese die Ferien und Festtage in Slowenien verbringe, vermöge nichts an der Quartierverbundenheit zu ändern. Zudem habe das Obergericht die notorische Tatsache verkannt, dass es für ein Kind äusserst nachteilig sei, während der ersten drei Primarschuljahren aus seinem gewohnten Umfeld herausgerissen zu werden.
11.5 Mit diesen Ausführungen vermag der Beschwerdeführer nicht aufzuzeigen, inwiefern das Obergericht das ihm bei der Bemessung der Erstreckung zustehende Ermessen überschritten haben soll, zumal das Obergericht weder die Quartierverbundenheit des Beschwerdeführers noch die Nachteiligkeit eines Kindergarten- bzw. Primarschulwechsels gänzlich verneinte, jedoch davon ausging, der Beschwerdeführer hätte durch die ihm zumutbare Aufnahme einer Erwerbstätigkeit während der Erstreckungsdauer seine finanzielle Situation verbessern und dadurch das Finden einer zumutbaren Wohnung ermöglichen können. Inwiefern diese Annahme unzutreffend sein soll, legt der Beschwerdeführer nicht dar.
12.
12.1 Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer grundsätzlich kostenpflichtig (<ref-law>). Er hat jedoch für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege beantragt. Diese ist gemäss <ref-law> zu gewähren, da die Bedürftigkeit des Beschwerdeführers aufgrund seiner Darlegungen und den eingereichten Unterlagen ausgewiesen ist und die Beschwerde nicht als von vornherein aussichtslos qualifiziert werden kann. Damit sind keine Gerichtskosten zu erheben (<ref-law>; Urteil 4A_336/2008 vom 2. September 2008 E. 6). Die Gewährung der unentgeltlichen Rechtspflege entbindet den Beschwerdeführer jedoch nicht von der Pflicht, die obsiegende Beschwerdegegnerin für das bundesgerichtliche Verfahren zu entschädigen (Art. 64 Abs. 1 und Art. 68 Abs. 2 BGG; Urteil 5P.170/2004 vom 1. Juli 2007, E. 2), weshalb dieser eine Parteientschädigung von Fr. 2'500.-- zuzusprechen ist.
12.2 Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Das Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege für das bundesgerichtliche Verfahren wird gutgeheissen.
2. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
3. Es werden keine Kosten erhoben.
4. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
5. Dieses Urteil wird den Parteien, dem Obergericht des Kantons Zürich, II. Zivilkammer, und dem Kassationsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 15. März 2010
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Gelzer