Sachverhalt:
A. A.a Am 14. März 1966 schloss die Y._ (Grundeigentümerin) mit Z._ sen. (Vater von Z._ jun., Beschwerdeführer) einen Baurechtsvertrag über die Bestellung eines selbstständigen und dauernden Baurechts auf dem Grundstück altKat.-Nr. xxx (Kat. Nr. yyy), Grundbuch A._. Das Grundstück wurde mit einem Zweifamilien-Terrassenhaus überbaut (B._strasse).
A.b Am 26. April 2001 stellte der Beschwerdeführer als Bauherr ein Gesuch für den Anbau einer Eingangshalle mit Nutzung des Flachdaches des oberen Hauses, wobei das Gesuch von der Grundeigentümerin und heutigen Beschwerdegegnerin mitunterzeichnet war. Der Gemeinderat von A._ bewilligte den Anbau, nicht aber den Dachausstieg mit Nutzung des Flachdaches (Beschluss vom 18. Juni 2001), im Wesentlichen mit der Begründung, die Grundeigentümerin (nachfolgend: Beschwerdegegnerin) habe die Zustimmung im Baugesuch zurückgezogen und den Dachausgang mit der Dachterrasse ausdrücklich verweigert. Die Rekurskommission des Kantons Zürich hiess den dagegen erhobenen Rekurs gut, weil die Beurteilung der Frage, ob die bauliche Massnahme mit dem Inhalt des Baurechtsvertrages vereinbar sei, in die Zuständigkeit der Zivilgerichte falle. Daraufhin erteilte der Gemeinderat A._ die Baubewilligung für das gesamte Projekt. In der Folge teilte die Beschwerdegegnerin dem Beschwerdeführer mit, sie verzichte auf eine Anfechtung der Baubewilligung, behalte sich jedoch vor, dem Baurechtsvertrag gegebenenfalls zivilrechtlich Nachachtung zu verschaffen. Der geplante Terrassenaufgang und die Nutzbarmachung der Dachfläche widerspreche klar dem Inhalt des Baurechtsvertrages.
B. In der Folge klagte der Beschwerdeführer vor dem gemäss Baurechtsvertrag bestellten Schiedsgericht gegen die Beschwerdegegnerin mit dem Begehren, es sei festzustellen, dass er gegenüber der Beschwerdegegnerin berechtigt sei, beim Wohnhaus Assek.-Nr. zzz, Kat.-Nr. yyy, B._strasse in A._ einen Dachaufgang sowie eine Dachterrasse gemäss bewilligter Baueingabe vom 26. April 2001 zu realisieren. Die Beschwerdegegnerin beantragte ihrerseits Abweisung der Klage und verlangte überdies mit abgeändertem Widerklagebegehren, es sei dem Beschwerdeführer unter Androhung der Ungehorsamsstrafe durch das zuständige Bezirksgericht zu untersagen, eine Erweiterung des bestehenden Dachausstiegs vorzunehmen und auf dem Flachdach Windschutzwände oder andere Vorrichtungen anzubringen, welche die bestehende 90 cm hohe Brüstung überragen. Das angerufene Schiedsgericht wies die Hauptklage ab und verbot dem Beschwerdeführer in Gutheissung der Widerklage, eine Erweiterung des bestehenden Dachausstiegs vorzunehmen und auf dem Flachdach Windschutzwände oder andere Vorrichtungen anzubringen, welche der Nutzbarmachung der Dachfläche als Dachterrasse dienen und das bestehende 110 cm hohe Brüstungsband überragen. Für den Fall der Zuwiderhandlung wurde Bestrafung wegen Ungehorsams gegen amtliche Verfügungen gemäss <ref-law> sowie der Zwangsvollzug angedroht (Urteil vom 30. Januar 2004). Die dagegen erhobene Nichtigkeitsbeschwerde wies das Obergericht des Kantons Zürich mit Beschluss vom 6. Mai 2004 ab, soweit es auf sie eintrat.
C. Mit staatsrechtlicher Beschwerde beantragt der Beschwerdeführer, sowohl das Urteil des Schiedsgerichts als auch den Beschluss des Obergerichts aufzuheben.
Das Obergericht hat auf Vernehmlassung verzichtet. Die Beschwerdegegnerin beantragt, die staatsrechtliche Beschwerde abzuweisen, soweit darauf eingetreten werden könne.

Das Bundesgericht zieht in Erwägung:
1. Das Obergericht hat als nach § 43 GVG (211.1) zuständige Gerichtsbehörde über die Nichtigkeitsbeschwerde nach Art. 36 ff. des Konkordates über die Schiedsgerichtsbarkeit (KSG; SR 279) beschlossen. Sein Beschluss gilt als letztinstanzlicher kantonaler Entscheid im Sinne von Art. 84 Abs. 1 OG i.V.m. Art. 86 Abs. 1 OG und kann daher mit staatsrechtlicher Beschwerde angefochten werden. Demgegenüber stellt das Urteil des Schiedsgerichts keinen kantonalen Endentscheid im Sinne von Art. 84 Abs. 1 OG dar und kann deshalb weder unmittelbar noch im Anschluss an einen kantonalen Rechtsmittelentscheid mit staatsrechtlicher Beschwerde angefochten werden (<ref-ruling> E. 1b). Soweit sich der Beschwerdeführer gegen das Urteil des Schiedsgerichts wendet, ist auf die staatsrechtliche Beschwerde nicht einzutreten.
2. Auf die staatsrechtliche Beschwerde ist ferner nicht einzutreten, soweit darin eine Verletzung von <ref-law> und <ref-law> gerügt wird. Der Beschwerdeführer legt nicht dar, inwiefern diese Verfassungsbestimmungen durch den angefochtenen Beschluss des Obergerichts verletzt worden sein sollen (Art. 90 Abs. 1 lit. b OG; <ref-ruling> E. d S. 201; <ref-ruling> E. 7a S. 312).
3. 3.1 Nach den Ausführungen des Obergerichts hat das Schiedsgericht erwogen, die Baurechtsgeberin habe sich mit dem Baurechtsvertrag vom 14. März 1966 eine geordnete Überbauung nach einheitlichen Kriterien sichern wollen, die auch im Falle nachträglicher Veränderungen gewahrt bleiben sollte. Das Obergericht hält alsdann dafür, die Feststellung des Schiedsgerichts, die Überbauung zeige noch heute ein "einheitliches Erscheinungsbild", sei nicht einfach die Feststellung einer Tatsache, wie der Beschwerdeführer argumentiere. Das Schiedsgericht habe im Rahmen der angeordneten Beweisabnahme von Amtes wegen einen Augenschein vor Ort sowie auf dem Grundbuchamt durchgeführt, habe überdies Einsicht in die Grundbuchakten genommen und an verschiedenen Standorten festgestellt, welcher Stellenwert dem Erscheinungsbild des Daches mit der streitbetroffenen Liegenschaft in der B._strasse zukomme. Die Parteien hätten zum protokollierten Ergebnis des Augenscheins Stellung bezogen. Der Beschwerdeführer rüge mit seiner Kritik an den Erwägungen des Schiedsgerichts willkürliche Beweiswürdigung und nicht willkürliche Tatsachenfeststellung. Die willkürliche Anwendung von Verfahrensrecht, hier des Grundsatzes der freien Beweiswürdigung, könne nicht mit Nichtigkeitsbeschwerde gemäss Art. 36 lit. f KSG geltend gemacht werden. Insoweit trat das Obergericht auf die Nichtigkeitsbeschwerde des Beschwerdeführers in diesem Punkt nicht ein.
3.2 Der Beschwerdeführer macht geltend, er habe im Rahmen der Nichtigkeitsbeschwerde die Annahme des Schiedsgerichts, das einheitliche Erscheinungsbild der Überbauung habe erhalten werden können, als willkürlich beanstandet. In der Nichtigkeitsbeschwerde sei nirgends die Rede davon gewesen, dass das Schiedsgericht eine Verfahrensvorschrift verletzt habe. Vielmehr sei eine willkürliche tatsächliche Annahme des Schiedsgerichtes gerügt worden, welche nach Art. 36 lit. f KSG nebst der Aktenwidrigkeitsrüge erhoben werden könne. Eine willkürliche tatsächliche Annahme liege namentlich dann vor, wenn das Gericht eine beweispflichtige Tatsache als bewiesen annehme, obwohl die Akten darüber keinen Aufschluss geben, oder wenn das Gericht eine Feststellung aufgrund willkürlicher Beweiswürdigung treffe. Die Auffassung des Obergerichts, bei der Rüge der willkürlichen tatsächlichen Annahme und der Rüge willkürlicher Beweiswürdigung handle es sich um unterschiedliche Nichtigkeitsgründe sei daher nicht nachvollziehbar. Die vor Obergericht erhobene Rüge habe sich auf die letztgenannte Variante, die willkürliche tatsächliche Annahme, bezogen, welche nach dem einschlägigen Kommentator (Frank/Sträuli/Messmer) einen Nichtigkeitsgrund im Sinne von Art. 36 lit. f KSG bilde. Die das Nichteintreten begründenden Erwägungen des Obergerichts äusserten sich nicht zu der von ihm (dem Beschwerdeführer) vorgebrachten Rüge und verletzten damit seinen Anspruch auf rechtliches Gehör im Sinne von <ref-law>.
3.3 Mit seinen Ausführungen beanstandet der Beschwerdeführer einmal im Ergebnis die Auslegung des Schiedsgerichts betreffend Art. 36 lit. f KSG und kritisiert alsdann auf dieser Rüge aufbauend eine Verletzung seines Anspruchs auf rechtliches Gehör. Aufgrund dieser Konstellation ist die Rüge der Auslegung von Art. 36 lit. f KSG mit Bezug auf die Nichtigkeitsgründe vorweg zu behandeln. Im Rahmen der staatsrechtlichen Beschwerde gemäss Art. 84 Abs. 1 lit. b OG prüft das Bundesgericht die Auslegung und Anwendung von Konkordatsrecht frei (<ref-ruling> E. 1 mit Hinweisen).
3.4 Nach Art. 36 lit. f KSG kann Nichtigkeitsbeschwerde erhoben werden, um geltend zu machen, "der Schiedsspruch sei willkürlich, weil er auf offensichtlich aktenwidrigen tatsächlichen Feststellungen beruht oder weil er eine offenbare Verletzung des Rechts oder der Billigkeit enthält". Die konkordatsrechtliche Umschreibung der Willkür stimmt im Ergebnis mit dem durch die bundesgerichtliche Rechtsprechung zu Art. 4 aBV - heute <ref-law> - entwickelten Willkürbegriff überein (Jolidon, Commentaire du Concordat suisse sur l'arbitrage, 1984, N. 93 zu Art. 36 KSG mit Hinweisen). Damit ist freilich noch nichts darüber ausgesagt, ob auch die Beweiswürdigung unter den Begriff der offensichtlich aktenwidrigen tatsächlichen Feststellung im Sinn von Art. 36 lit. f KSG zu subsumieren ist. Diese Bestimmung umfasst den Willkürtatbestand nicht generell, sondern konkretisiert ihn nach drei Richtungen: Willkürlich ist ein Schiedsspruch, wenn er auf (1) offensichtlich aktenwidrigen Feststellungen beruht, wenn er (2) materielles Recht oder (3) den Grundsatz der Billigkeit offensichtlich verletzt (Poudret, SJK 464c S. 5).
3.5 In <ref-ruling> E. 5a/aa hat das Bundesgericht freilich ausgeführt, die kantonalen Behörden könnten im Rahmen einer Beschwerde gestützt auf Art. 36 lit. f KSG in die Beweiswürdigung der Schiedsgerichte nur eingreifen, wenn sie sich als offensichtlich falsch bzw. willkürlich erweise oder auf einem offensichtlichen Versehen beruhe. Allerdings hat sich das Bundesgericht, wie den Erwägungen zu entnehmen ist, mit der Auslegung von Art. 36 lit. f KSG nicht befasst und sich insoweit zur hier zu beurteilenden Streitfrage nicht geäussert.
Nach Lalive/Poudret/Reymond (Le droit de l'arbitrage, 1989, N. 4 zu Art. 36 KSG S. 213 f.) umfasst Art. 36 lit. f KSG auch die Beweiswürdigung, namentlich die Würdigung von Aktenstücken, wie protokollierte Zeugenaussagen und Expertisen. Sie stützen ihre Auffassung auf die besagte Erwägung (5a/aa) des bundesgerichtlichen Urteils.
Jolidon (Commentaire du Concordat suisse sur l‘arbitrage, 1984, S. 517; Derselbe, Les motifs du recours en nullité selon le Concordat suisse sur l‘arbitrage, in: Berner Festgabe zum Schweizerischen Juristentag 1979, S. 326), gemäss dem auch die offensichtlich unrichtige Beweiswürdigung Gegenstand der Prüfung gemäss Art. 36 lit. f KSG bildet, beruft sich ebenfalls auf die erwähnte Rechtsprechung, aber auch auf <ref-law>/BE. Diese Bestimmung nennt allerdings den Nichtigkeitsgrund der offenbar unrichtigen Beweiswürdigung ausdrücklich, weshalb daraus für die Auslegung von Art. 36 lit. f KSG nichts zu gewinnen ist.
Schliesslich verweist der Beschwerdeführer auf den Kommentar zur zürcherischen Zivilprozessordnung (Frank/Sträuli/Messmer, Kommentar zur zürcherischen Zivilprozessordnung, 3. Aufl. Zürich 2000, N. 106 vor §§ 238 - 258 ZPO/ZH), wo ausgeführt wird, die Aktenwidrigkeitsrüge decke sich mit dem Nichtigkeitsgrund von § 281 Ziff. 2, erster Teil (aktenwidrige tatsächliche Annahme) und die willkürliche tatsächliche Annahme entspreche dem Nichtigkeitsgrund von § 281 Ziff. 2, zweiter Teil (willkürliche tatsächliche Annahme). Richtig ist, dass die willkürliche tatsächliche Annahme auch die Beweiswürdigung umfasst (Frank/Sträuli/Messmer, a.a.O., N. 45 zu <ref-law>/ZH). Doch übersehen die Autoren, dass Art. 36 lit. f KSG - im Gegensatz zu § 281 Ziff. 2 - den Nichtigkeitsgrund gerade nicht mit der "willkürlichen tatsächlichen Annahme" umschreibt, sondern mit der Willkür, die auf einer offenbaren Verletzung von Recht und Billigkeit sowie auf "offensichtlich aktenwidrigen Feststellungen" beruht.
3.6 Offensichtlich aktenwidrige tatsächliche Feststellungen trifft das Schiedsgericht dann, wenn es sich infolge Versehens mit den Akten in Widerspruch gesetzt hat, sei es, dass es Aktenstellen übersehen oder ihnen einen anderen als den wirklichen Inhalt beigemessen hat, sei es, dass es irrig davon ausgegangen ist, eine Tatsache sei aktenmässig belegt, während die Akten in Wirklichkeit darüber keinen Aufschluss geben (Rüede/Hadenfeldt, Schweizerisches Schiedsgerichtsrecht, 2. Aufl., 1993, S. 346; in diesem Sinne auch der Entscheid 4P.138/1997 vom 29. Oktober 1997, E. 1). Aktenwidrigkeit ist nicht mit Beweiswürdigung gleichzusetzen, sondern liegt nur vor, wenn der Richter bei der Beweiswürdigung von unrichtigen tatsächlichen Prämissen ausgeht (so Guldener, Schweizerisches Zivilprozessrecht, 3. Aufl. 1979, S. 523, Fn. 28 lit. b; siehe auch Messmer/Imboden, Die eidgenössischen Rechtsmittel in Zivilsachen, Nr. 149 Fn. 42, S. 213 und BGE 63 II 39 betreffend Auslegung von Art. 81 aOG). Nicht das Ergebnis der Beweiswürdigung und die darin liegenden Wertungen sind Gegenstand der Willkürrüge, sondern durch Akten unstreitig widerlegte Tatsachenfeststellungen (Wenger, Die Rechtsmittel gegen schiedsrichterliche Entscheidungen gemäss Konkordat und gemäss zürcherischem Recht, in: Die Internationale Schiedsgerichtsbarkeit der Schweiz, Band I, S. 67 f.).
3.7 Dieses Auslegungsergebnis erweist sich auch unter rechtspolitischen Gesichtspunkten als sachgerecht: Was die tatsächlichen Feststellungen anbelangt, sind mögliche Rügen auf klare Fälle beschränkt. Ob eine tatsächliche Annahme offensichtlich aktenwidrig ist, ist keine Wertungs-, keine Ermessensfrage. Demgegenüber beruht die Beweiswürdigung oft auf Ermessen und ebenso die Beurteilung der Frage, ob dieses Ermessen willkürlich gehandhabt wurde. Es macht durchaus Sinn, bei der Überprüfung von Schiedssprüchen dieses schwer fassbare Feld auszusparen. Wer seinen Streit einem Schiedsgericht unterbreitet, hat dessen Beweiswürdigung hinzunehmen, nicht jedoch offensichtlich aktenwidrige tatsächliche Feststellungen. Vergleichsweise sei auf das Verfahren der internationalen Schiedsgerichtsbarkeit hingewiesen, dessen Beschwerdegrund der Verletzung des Ordre public gemäss <ref-law> die Anfechtungsmöglichkeiten im Vergleich zu Art. 36 lit. f KSG erheblich einschränkt, indem selbst eine offensichtlich aktenwidrige Tatsachenfeststellung oder eine offenbare Verletzung des Rechts für sich allein nicht ausreicht, um ein Schiedsurteil aufzuheben (<ref-ruling> E. 4 S. 636, 115 II 102 E. 3a S. 105).
3.8 Die I. Zivilabteilung des Bundesgerichts hat dieser Rechtsauffassung im Verfahren nach Art. 16 OG zugestimmt.
3.9 Im vorliegenden Fall wurde über den Augenschein ein Protokoll erstellt. Dazu haben die Parteien Stellung nehmen können, wobei der Beschwerdeführer nach den obergerichtlichen Feststellungen keine Änderungen bzw. Korrekturen beantragt hat. Alle weiter gehenden Ergebnisse des Augenscheins, namentlich die aus den feststehenden Wahrnehmungen zu ziehenden Schlüsse sowie die darauf gestützten Wertungen sind Bestandteil der Beweiswürdigung (Bühler, Die Beweiswürdigung, in: Der Beweis im Zivilprozess, 2000, S. 85). Aus dem obergerichtlichen Beschluss und dem Schiedsgerichtsurteil ergibt sich, dass das Schiedsgericht seine Feststellung, die Überbauung zeige noch heute ein "einheitliches Erscheinungsbild", in Würdigung der Wahrnehmungen anlässlich des Augenscheines getroffen hat. Auf Beweiswürdigung beruhend ist dieser Schluss der Aktenwidrigkeitsrüge nicht zugänglich und daher mit Nichtigkeitsbeschwerde nicht anfechtbar. Ist aber das Obergericht zu Recht auf die Rüge des Beschwerdeführers nicht eingetreten, bleibt auch die Rüge der Verletzung von <ref-law> erfolglos.
4. Der Beschwerdeführer macht ferner geltend, es sei unzutreffend, dass er mit Bezug auf die Wintergärten eine Unvollständigkeit des Protokolls über den Augenschein gerügt habe; vielmehr habe er auf die darin festgehaltenen Wintergärten hingewiesen und geltend gemacht, dass diese baulichen Veränderungen bei der Beurteilung des Erscheinungsbildes überhaupt nicht berücksichtigt worden seien, obwohl sie offensichtlich eine Vergrösserung des Bauvolumens und einen starken Eingriff in die Gestalt, insbesondere die Fassade der Bauten bedeutet hätten und auch daher die Annahme eines hinsichtlich Gestalt und Grösse einheitlich gebliebenen Erscheinungsbildes willkürlich sei. Das Obergericht habe daher auch insoweit seinen Anspruch auf rechtliches Gehör verletzt, indem es seine Rüge nicht richtig zur Kenntnis genommen habe und daher nicht darauf eingetreten sei.
Es trifft zu, dass im Protokoll über den Augenschein die angesprochenen Wintergärten aufgeführt sind und der Beschwerdeführer die nunmehr vorgetragene Rüge bereits vor Obergericht vorgebracht hat. Das ändert aber nichts daran, dass die namentlich aufgrund der Eindrücke des Augenscheines getroffene Feststellung, bei der Überbauung B._strasse habe das einheitliche Erscheinungsbild, insbesondere auch in Bezug auf die Dachlandschaft, bis heute gewahrt werden können, die Beweiswürdigung beschlägt. Auch diesbezüglich erweist sich die Rüge der Verletzung des rechtlichen Gehörs als unbegründet.
5. Damit ist die staatsrechtliche Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 156 Abs. 1 und Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtsgebühr von Fr. 5‘000.-- wird dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 6‘000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, III. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 18. November 2004
Im Namen der II. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: