Sachverhalt:
A. Mit Vertrag vom 14. Mai 2002 mietete B._ (Kläger) von der A._ AG (Beklagte) per 1. Juli 2002 einen 5-Zimmer-Hausteil mit Garten und Gartensitzplatz in Meilen zu einem monatlichen Mietzins von Fr. 2'365.--. Am 29. September 2003 stellte die Beklagte dem Kläger eine Heizkostenabrechnung zu, worauf der Kläger mit Schreiben vom 7. Oktober 2003 an die Beklagte gelangte und um Zustellung einer korrekten Heizkostenabrechnung ersuchte.
B. Am 27. November 2003 reichte der Kläger bei der Schlichtungsstelle des Bezirkes Meilen Klage ein mit dem Rechtsbegehren, es sei der Mietzins angemessen herabzusetzen und es sei eine ordnungsgemässe Heizkostenabrechnung für die vorangehende Heizperiode zu erstellen. Da keine Einigung zustande kam, gelangte der Kläger am 30. Januar 2004 an das Mietgericht, welches mit Beschluss vom 18. Mai 2004 auf das Begehren um Herabsetzung nicht eintrat und dasjenige betreffend die Heizkostenabrechnung als gegenstandslos abschrieb. Ein dagegen vom Kläger erhobener Rekurs wurde vom Obergericht des Kantons Zürich mit Beschluss vom 16. September 2004 gutgeheissen und die Sache (zur materiellen Entscheidung) an die Vorinstanz zurückgewiesen. Mit Urteil vom 18. August 2005 trat das Mietgericht nunmehr auf die Klage ein und setzte den Mietzins von Fr. 2'365.-- per 1. April 2004 um 6,5 Prozent auf Fr. 2'211.-- herab. Auf Berufung der Beklagten hin wurde dieser Entscheid vom Obergericht des Kantons Zürich mit Beschluss vom 13. April 2006 bestätigt.
C. Mit Berufung vom 24. Mai 2006 beantragt die Beklagte dem Bundesgericht, der Beschluss des Obergerichts des Kantons Zürich vom 13. April 2006 sei mit Ausnahme von Ziffer 1 des Dispositivs aufzuheben und auf die Klage betreffend Herabsetzung des Mietzinses sei nicht einzutreten.
Der Kläger beantragt sinngemäss Abweisung der Berufung. Gleichzeitig stellt er den Antrag auf unentgeltliche Prozessführung und Bestellung eines unentgeltlichen Rechtsbeistandes.

Das Bundesgericht zieht in Erwägung:
1. Mit ihrer Berufung macht die Beklagte zusammengefasst geltend, die Auffassung der Vorinstanz, wonach sich das Vorverfahren gemäss <ref-law> bei bestehenden Meinungsverschiedenheiten erübrige, sei unhaltbar und verletze Bundesrecht. Wenn der Kläger die Beklagte vorgängig um Herabsetzung des Mietzinses ersucht hätte, so wäre die Beklagte diesem Wunsch nachgekommen. Es hätten keine Umstände vorgelegen, die eine weitere Ausnahme von der Pflicht begründet hätten, vorgängig ein schriftliches Gesuch um Herabsetzung zu stellen. Die Durchführung eines solchen Vorverfahrens sei als Prozessvoraussetzung zu betrachten, weshalb auf die Klage nicht einzutreten sei.
2. <ref-law> regelt die Anfechtung des Mietzinses und dessen Herabsetzung während der Mietdauer. Gemäss <ref-law> muss der Mieter das Herabsetzungsbegehren schriftlich beim Vermieter stellen, worauf dieser innert 30 Tagen Stellung zu nehmen hat. Entspricht der Vermieter dem Begehren nicht oder nur teilweise oder antwortet er nicht fristgemäss, so kann der Mieter innert 30 Tagen die Schlichtungsbehörde anrufen. Dieses parteiinterne Vorverfahren ist gemäss <ref-law> nicht erforderlich, wenn der Mieter gleichzeitig mit der Anfechtung einer Mietzinserhöhung ein Herabsetzungsbegehren stellt.
3. Die Vorinstanz wies darauf hin, dass in der Lehre überwiegend die Auffassung vertreten werde, <ref-law> stelle eine bundesrechtliche Prozessvoraussetzung auf. Zwar habe das Bundesgericht in <ref-ruling> die Formvorschriften für die Mietzinsherabsetzung (an den Vermieter gerichtetes schriftliches Begehren, Abwarten der Antwort während einer bestimmten Frist und anschliessende fristgemässe Einleitung des Schlichtungsverfahrens) als blosse Ordnungsvorschriften bezeichnet. Es habe erwogen, der Vermieter bleibe bei einer Erhöhungsanzeige für das spätere Verfahren an seine förmliche Erklärung gebunden, während das parteiinterne Vorverfahren gemäss <ref-law> lediglich bezwecke, die Parteien vor der Einleitung eines behördlichen Verfahrens zu einem Meinungsaustausch über den künftigen Mietzins zu veranlassen, weshalb sich die Parteien nicht bereits im Vorverfahren endgültig festlegen müssten und im nachfolgenden behördlichen Verfahren an ihre Erklärungen im Vorverfahren nicht gebunden seien. Dabei habe sich das Bundesgericht nicht zur Frage geäussert, ob die Durchführung des parteiinternen Vorverfahrens gemäss <ref-law> Voraussetzung für die Einleitung des Schlichtungsverfahrens sei. Es erwäge indessen, dass die Vorschrift von <ref-law> auf der Überlegung beruhe, ein auf die gütliche Einigung ausgerichtetes Vorverfahren sei nicht mehr sinnvoll, wenn die Parteien bereits in einem Anfechtungsverfahren über den Mietzins stritten. Daraus könne geschlossen werden, es betrachte die Durchführung des Vorverfahrens ebenfalls als Prozessvoraussetzung, welche nur in wenigen Fällen unbeachtet bleiben dürfe. Im erwähnten Entscheid sei es denn auch zum Schluss gelangt, dass neben der Ausnahmebestimmung von <ref-law> ein weiterer Ausnahmefall dann gegeben sei, wenn während der Hängigkeit eines Herabsetzungsverfahrens neue Herabsetzungsgründe einträten. Dies lasse ebenfalls darauf schliessen, dass es grundsätzlich ein Vorverfahren als notwendig erachte. Als weiterer Ausnahmefall für die Nichtbeachtung von <ref-law> fällt für die Vorinstanz in Betracht, wenn der Vermieter von vornherein kundgetan hat, er sei nicht bereit, den Mietzins zu senken. Als Beispiel würden die Fälle genannt, wenn der Vermieter auf das Gesuch des Mieters hin mit einer formkorrekten Mietzinserhöhung antworte oder sich das Senkungsbegehren und die Erhöhungsanzeige in der Zustellung "kreuzen" würden. Ein genau gleich gelagerter Fall sei hier zwar nicht gegeben. Es lägen aber besondere Umstände vor: Zwischen den Parteien seien mit Bezug auf das von ihnen abgeschlossene Mietverhältnis schon zahlreiche Verfahren hängig gewesen und es sei ein erstes Mal bereits am 30. Oktober 2003 und damit vor der Anhängigmachung des Herabsetzungsbegehrens eine Kündigung erfolgt. In der Folge seien nochmals zwei Kündigungen ausgesprochen worden. Angesichts der zahlreichen zwischen den Parteien im Zeitpunkt der Stellung des Herabsetzungsbegehrens bereits bestehenden Meinungsverschiedenheiten erscheine ein Vorverfahren mit dem Zweck einer Einigung als sinnlos.
4. Wie die Vorinstanz zu Recht festhält, hat sich das Bundesgericht bisher nicht ausdrücklich zur Frage geäussert, ob die Durchführung des parteiinternen Vorverfahrens gemäss <ref-law> Voraussetzung für die Einleitung des Schlichtungsverfahrens ist.
4.1 In <ref-ruling> wurde unter Hinweis auf eine Literaturstelle ausgeführt, bei den Anforderungen gemäss <ref-law> handle es sich bloss um Ordnungsvorschriften. Das parteiinterne Vorverfahren bezwecke lediglich, die Parteien vor der Einleitung eines behördlichen Verfahrens zu einem Meinungsaustausch über den künftigen Mietzins zu veranlassen. Diese Feststellung erfolgte im Hinblick auf die Frage, ob die Parteien sich bereits im Vorverfahren endgültig festlegen müssten und im nachfolgenden behördlichen Verfahren an ihre Erklärungen im Vorverfahren gebunden seien, was verneint wurde (a.a.O., E. 4c S. 24). Das Bundesgericht hielt fest, <ref-law> sei vor diesem Hintergrund zu sehen. Danach könne der Mieter gleichzeitig mit der Anfechtung einer Mietzinserhöhung ein Herabsetzungsbegehren stellen, ohne vorgängig das Vorverfahren gemäss <ref-law> in Gang setzen zu müssen. Die Vorschrift beruhe auf der Überlegung, dass ein Vorverfahren, das eine gütliche Einigung ermöglichen soll, nicht mehr sinnvoll sei, wenn die Parteien bereits in einem Anfechtungsverfahren über den Mietzins streiten würden. Dieser Gedanke treffe aber auch dann zu, wenn neue Herabsetzungsgründe einträten, während bei den Behörden bereits ein Herabsetzungsverfahren hängig sei. Es rechtfertige sich daher, dem Mieter in analoger Anwendung von <ref-law> auch in solchen Fällen die Möglichkeit einzuräumen, neue Herabsetzungsforderungen ohne vorgängiges Parteiverfahren im Sinne von <ref-law> in das laufende behördliche Verfahren einzubringen, solange das kantonale Prozessrecht dies zulasse (a.a.O., E. 4c S. 24 f.).
4.2 Aus dem Dargelegten ergibt sich, dass sich das Bundesgericht zur Frage äusserte, ob zusätzliche Gründe denkbar sind, welche - über den Wortlaut von <ref-law> hinausgehend - den Ausschluss des parteiinternen Vorverfahrens erlauben. Damit wurde aber gleichzeitig vorausgesetzt, dass ein solches Verfahren grundsätzlich notwendig ist. Wenn im erwähnten <ref-ruling> die Frage zu entscheiden war, ob neue Herabsetzungsgründe unter den Ausnahmetatbestand von <ref-law> fallen, so war davon auszugehen, dass im Verneinungsfall ein vorgängiges Parteiverfahren unerlässlich ist. Der Hinweis, es handle sich um Ordnungsvorschriften, bezog sich auf die einzelnen Formerfordernisse des <ref-law>, nämlich das an den Vermieter gerichtete schriftliche Begehren, das Abwarten der Antwort während einer bestimmten Frist und die anschliessende fristgemässe Einleitung des Schlichtungsverfahrens. Es ist einzuräumen, dass die mit Verweis auf eine Literaturstelle gewählte Formulierung zu Missverständnissen führen könnte. Es sollte damit einzig zum Ausdruck gebracht werden, dass das Einleitungsverfahren zur Mietzinsherabsetzung im Gegensatz zum Erhöhungsverfahren nur informellen Charakter hat mit dem Zweck, einen Meinungsaustausch zwischen den Parteien anzuregen (Roger Weber, Basler Kommentar, 3. Aufl., Basel 2003, N. 6a zu <ref-law>). Die Lehre geht mehrheitlich zu Recht davon aus, dass das in <ref-law> vorgesehene Parteiverfahren als eigentliche Prozessvoraussetzung zwingend eingehalten werden muss, sofern nicht ein Ausnahmefall gemäss <ref-law> vorliegt (Peter Higi, Zürcher Kommentar, Zürich 1998, N. 6 zu <ref-law>; SVIT-Kommentar zum Mietrecht, 2. Aufl., Zürich 1998, N. 28 zu <ref-law>). Das Bundesgericht hat in einem unveröffentlichten Entscheid dieses private Einleitungsverfahren ebenfalls als Prozessvoraussetzung bezeichnet (Urteil 4C.328/2005 vom 9. Dezember 2005, E. 3). Wie erwähnt soll es die Parteien vor der Einleitung eines behördlichen Verfahrens zu einem Meinungsaustausch über den künftigen Mietzins veranlassen (<ref-ruling> E. 4c S. 24). Es dient im Wesentlichen dazu, das Herabsetzungsverfahren zu vermeiden, indem der Vermieterschaft vor Einleitung des Schlichtungsverfahrens die Möglichkeit zur freiwilligen Reduktion des Mietzinses eröffnet werden soll (Urteil 4C.411/1994 vom 14. September 1995, E. 3b). Das Vorverfahren kann für den Vermieter von praktischer Bedeutung sein. Würde dieser nämlich ohne weiteres in ein Schlichtungs- oder Gerichtsverfahren hineingezogen, könnte dies bei einer gütlichen Einigung mit dem Mieter zu einer Kündigungssperre führen (Art. 271a Abs. 1 lit. e Ziff. 4 OR). Dies kann er verhindern, indem er im parteiinternen Vorverfahren dem Anliegen des Mieters nachkommt.
4.3 Die Vorinstanz hat somit zu Recht die Durchführung des Vorverfahrens als eigentliche Prozessvoraussetzung betrachtet. Damit stellt sich im Folgenden die Frage, ob im vorliegenden Fall im Hinblick auf <ref-law> auf ein solches parteiinternes Einleitungsverfahren verzichtet werden konnte. Das Bundesgericht hat den Anwendungsbereich dieser Ausnahmebestimmung in dem Sinne erweitert, als neue Herabsetzungsforderungen in das laufende behördliche Verfahren eingebracht werden können (<ref-ruling> E. 1 c S. 25). Nach dem Sinn und Zweck von <ref-law> erübrigt sich ein Vorverfahren mit dem Ziel, eine gütliche Einigung zu erzielen, wenn die Parteien bereits in einem Anfechtungsverfahren über den Mietzins streiten. Gleich verhielte es sich, wenn der Vermieter von vorneherein klar kundgetan hätte, er sei nicht bereit, den Mietzins zu senken (Higi, a.a.O., N. 7 zu <ref-law>). Als Ausnahmebestimmung und auch angesichts des klaren Wortlautes ist <ref-law> indessen nicht unbesehen zu erweitern. Andernfalls besteht die Gefahr, die grundsätzliche Bedeutung des vorgängigen Parteiverfahrens zu relativieren und dessen Sinn in Frage zu stellen. Wenn die Vorinstanz festhält, es lägen im hier zu beurteilenden Fall besondere Umstände vor, so lässt sich daraus für eine analoge Anwendung der gesetzlichen Ausnahmebestimmung noch nichts ableiten. Dass mit Bezug auf das zwischen den Parteien abgeschlossene Mietverhältnis schon zahlreiche Verfahren hängig sind und es bereits zu Kündigungen gekommen ist, weist zwar auf bestehende Meinungsverschiedenheiten hin. Darüber hinaus kann aber nicht zwingend geschlossen werden, eine Einigung über die neu in Frage stehende Herabsetzung des Mietzinses sei von vorneherein unmöglich und ein Vorverfahren damit sinnlos. Es ging um Berechnungsgrundlagen, die sich geändert hatten und an sich zu einer Reduktion des Mietzinses führen mussten. Wenn der Mietzins trotz Hypothekarzinssenkung unverändert bleiben sollte, so lag es an der Beklagten, die Gründe dafür darzutun. Dieser Obliegenheit hätte sie ungeachtet anderer Meinungsverschiedenheiten nachkommen müssen. Es war in ihrem Interesse, gegenteilige Argumente vorzubringen, falls sie sich der Meinung des Klägers hätte widersetzen wollen. War dessen Anliegen dagegen berechtigt, so ist nicht einzusehen, weshalb die Beklagte hätte unnachgiebig bleiben und ein nachteiliges Gerichtsverfahren in Kauf nehmen sollen. Auf jeden Fall fehlten konkrete Anhaltspunkte dafür, dass sich die Beklagte trotz der neuen Berechnungsgrundlage von vorneherein gegen eine Herabsetzung des Mietzinses gewehrt hätte.
4.4 Somit hätte der Kläger gestützt auf <ref-law> der Beklagten zunächst Gelegenheit geben müssen, zum Herabsetzungsbegehren Stellung zu nehmen. Weil er dies unterliess, war er nicht berechtigt, Klage beim Mietgericht einzureichen. Indem das Obergericht trotz der fehlenden Prozessvoraussetzung auf die Klage eintrat, verletzte es Bundesrecht, was zur Aufhebung des vorinstanzlichen Entscheides und zum Nichteintreten auf die Klage führt. Im Übrigen ist das Verfahren zur Regelung der Kosten- und Entschädigungsfolgen im kantonalen Verfahren an die Vorinstanz zurückzuweisen.
5. Der Kläger hat für das Verfahren vor Bundesgericht das Gesuch um unentgeltliche Prozessführung und um Bestellung eines unentgeltlichen Rechtsvertreters gestellt. Einer bedürftigen Partei, deren Standpunkt nicht aussichtslos erscheint, kann die unentgeltliche Rechtspflege gewährt und nötigenfalls ein unentgeltlicher Rechtsbeistand beigegeben werden (Art. 152 Abs. 2 OG). Dem Gesuch des Klägers, der als bedürftig anzusehen ist, kann entsprochen werden, weil sein Prozessstandpunkt nicht aussichtslos war und unter den gegebenen Umständen eine anwaltliche Vertretung geboten erscheint. Wenn der Kläger später dazu imstande ist, hat er der Bundesgerichtskasse für die Entschädigung des unentgeltlichen Rechtsvertreters Ersatz zu leisten (Art. 152 Abs. 3 OG).
Im Übrigen hat der unterliegende Kläger die Beklagte für das bundesgerichtliche Verfahren zu entschädigen (Art. 159 Abs. 1 und 2 OG).

Demnach erkennt das Bundesgericht:
1. Das Gesuch des Klägers um Gewährung der unentgeltlichen Rechtspflege wird gutgeheissen und es wird ihm Rechtsanwalt Ervin Deplazes, Stäfa, als unentgeltlicher Rechtsbeistand beigegeben.
2. Die Berufung wird gutgeheissen und das Urteil des Obergerichtes des Kantons Zürich vom 13. April 2006 wird aufgehoben.
3. Auf die Klage wird nicht eingetreten.
4. Es werden keine Gerichtskosten erhoben.
5. Der Kläger hat die Beklagte für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
6. Dem Anwalt des Klägers, Ervin Deplazes, Stäfa, wird aus der Bundesgerichtskasse ein Honorar von Fr. 2'500.-- ausgerichtet.
7. Die Sache wird zur Neuregelung der Kosten- und Entschädigungsfolgen ans Obergericht des Kantons Zürich zurückgewiesen.
8. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 7. September 2006
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: