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 Art. 292 StGB 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.