Sachverhalt:
A. Die Stadt Zürich plant seit Längerem, auf ihrem Gemeindegebiet entlang des Zürichseeufers einen durchgehenden Seeuferweg zu realisieren. Am 19./20. März 2008 erfolgte die Amtsblattpublikation und vom 25. März bis 24. April 2008 die öffentliche Auflage von Plänen zum Bau eines Stegs zwischen der Roten Fabrik und dem Hafen Wollishofen. Das Projekt umfasst eine 284 Meter lange, 2,8 Meter breite und im Abstand von 15 Metern auf Pfählen fundierte Stahlkonstruktion mit bogenförmigem, mehrfach geknicktem Verlauf. Die Plätze am Ufer bei den Steganschlüssen sollen neu gestaltet werden. Als ökologische Ersatzmassnahmen, die aufgrund negativer Beschattungseffekte des Stegbaus erforderlich sind, ist vorgesehen, eine bestehende Ufertreppe abzubrechen, mittels Kiesschüttung ein Flachufer zu gestalten und ein Brutfloss für Flussseeschwalben zu erstellen.
Am 17. Juni 2009 wies der Zürcher Stadtrat mehrere gegen das Stegbauprojekt eingegangene Einsprachen ab, verwies die vorsorglich angemeldeten Entschädigungsforderungen in das Schätzungsverfahren, beschloss die Festsetzung des Seeuferwegprojekts gemäss Auflageplan und auferlegte den Einsprechenden die Verfahrenskosten. Gleichzeitig eröffnete der Stadtrat auch die Verfügung der Baudirektion vom 6. April 2009 sowie eine am 22. April 2009 wiedererwägungsweise beschlossene Dispositivänderung. Mit diesen Verfügungen hatte die Baudirektion des Kantons Zürich der Stadt Zürich für das Stegprojekt unter Auflage zahlreicher Nebenbestimmungen eine wasserrechtliche Konzession, eine fischereigesetzliche Bewilligung, eine raumplanungsrechtliche Ausnahmebewilligung für Bauten ausserhalb von Bauzonen, eine Bewilligung aufgrund der Landanlagekonzession sowie eine wasserbaupolizeiliche Ausnahmebewilligung erteilt.
B. X._, Y._ und Z._ erhoben am 31. Juli 2009 Rekurs gegen die Verfügung des Stadtrats vom 17. Juni 2009. Am 23. Juni 2010 wies der Regierungsrat des Kantons Zürich den Rekurs ab, soweit darauf eingetreten werde.
Dagegen erhoben die Rekurrenten am 13. September 2010 Beschwerde beim Verwaltungsgericht des Kantons Zürich; sie machten unter anderem geltend, der angefochtene Entscheid sei unter Missachtung von Ausstandsbestimmungen zustande gekommen. Am 13. Januar 2010 hiess das Verwaltungsgericht die Beschwerde teilweise gut und wies die Sache zu neuem Entscheid in rechtskonformer Zusammensetzung des Spruchkörpers an den Regierungsrat zurück.
C. Mit Beschluss vom 17. August 2011 entschied der Regierungsrat erneut, ohne den im Ausstand befindlichen Baudirektor. Er wies den Rekurs abermals ab, soweit darauf eingetreten werde.
Dagegen erhoben X._, Y._ und Z._ am 24. September 2011 Beschwerde ans Verwaltungsgericht. Sie beantragten in der Hauptsache, auf den geplanten Steg sei zu verzichten; eventualiter verlangten sie diverse Projektänderungen.
Am 21. Dezember 2011 wies das Verwaltungsgericht die Beschwerde ab, soweit es darauf eintrat.
D. Gegen den verwaltungsgerichtlichen Entscheid haben drei Eigentümer von Grundstücken im Bereich des projektierten Stegs - X._, Y._ und Z._ - am 6. Februar 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Sie beantragen, der angefochtene Entscheid sei, zusammen mit der Festsetzung des Stadtrats Zürich vom 17. Juni 2009 und den Verfügungen der Baudirektion vom 6. bzw. 22. April 2009, aufzuheben.
Eventualiter verlangen sie:
a) der Steg sei höchstens 1,5 Meter breit möglichst wassernah mit einem Durchlass für Schiffe und in einem einzigen Bogen ohne jedwede Aufenthaltsflächen zu gestalten und die Passage sei täglich bei Einbruch der Dunkelheit von beiden Seiten zu verschliessen,
b) die Ausgleichsmassnahmen auf dem südlichen Gelände der Henneberg'schen Seidenweberei seien so auszugestalten, dass der Bucht die überbaute Wasserfläche wieder zugeführt werde,
c) auf die beidseits des Stegs geplanten Anpassungs- und Neugestaltungsarbeiten sei zu verzichten, insbesondere auf das Fällen der grossen Bäume, subeventualiter sei zumindest die bestehende Bepflanzung mit den grossen alten Pappeln zu belassen und in die Gestaltung einzubeziehen,
d) auf die Umgestaltung der Hafenanlage im angrenzenden Bereich des geplanten Stegs sei zu verzichten, insbesondere auf die Neupflanzung von Säulenpappeln und die Errichtung einer "Begegnungszone", und
e) es seien die Entwertungen der Anrainergrundstücke infolge der neuen Immissionen ebenso materiell zu entschädigen wie die faktische Enteignung durch die Erschwerung bis Verunmöglichung (Hochwasser, Boote mit Aufbau) der Zufahrt zu den Bootshäusern; subeventualiter sei festzustellen, dass die Beschwerdeführenden ihre Ansprüche rechtzeitig geltend gemacht hätten und dass Unfreiwilligkeit im Sinne von § 13 des Zürcher Gesetzes vom 30. November 1879 betreffend die Abtretung von Privatrechten (AbtrG) vorliege.
Für den Fall der Rückweisung stellen die Beschwerdeführer folgende Anträge:
1. Die Stadt Zürich sei anzuweisen, das Projekt ordnungsgemäss auszustecken und danach nochmals öffentlich auszuschreiben,
2. es sei aufgrund des konkreten Projekts ein neues Gutachten der Natur- und Heimatschutzkommission (NHK) einzuholen, und es sei eine Umweltverträglichkeitsprüfung (UVP) anzuordnen,
3. es sei ein gerichtlicher Augenschein durchzuführen; eventualiter (bei Nichtrückweisung) ein bundesgerichtlicher Augenschein.
E. Die Stadt Zürich schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Amt für Verkehr des Kantons Zürich verweist auf den Rekursentscheid des Regierungsrats vom 17. August 2011.
Das Bundesamt für Umwelt (BAFU) äussert sich in seiner Vernehmlassung zu den umweltrechtlichen Rügen der Beschwerdeführer, ohne formell Antrag zu stellen. Das Bundesamt für Raumentwicklung (ARE) hat auf eine Vernehmlassung verzichtet.
In ihrer Replik halten die Beschwerdeführer an ihren Anträgen fest.
F. Mit Verfügung vom 6. März 2012 wurde das Gesuch um Gewährung der aufschiebenden Wirkung abgewiesen.

Erwägungen:
1. Da alle Sachurteilsvoraussetzungen vorliegen, ist auf die Beschwerde einzutreten.
2. Die Beschwerdeführer erheben mehrere Verfahrensrügen.
2.1 Sie rügen eine Verletzung des rechtlichen Gehörs, weil das Verwaltungsgericht auf ihre Rüge, das Seestegprojekt sei mangelhaft ausgesteckt worden, nicht eingegangen sei.
Die Vorinstanz ging davon aus, dass jedenfalls die Beschwerdeführer von dem mittels Bojen ausgesteckten Stegprojekt Kenntnis hatten und sich durch den öffentlich aufgelegten, massstabgetreuen Plan des Bauvorhabens über dessen Dimensionen informieren und rechtzeitig Einsprache bzw. Rekurs erheben konnten. Unter diesen Umständen sei nicht ersichtlich, welchen praktischen Nutzen sie aus einer erneuten Bekanntmachung ziehen könnten. Auf ein allfälliges Interesse Dritter an einer erneuten Aussteckung könnten sie sich nicht berufen.
Diese Erwägungen entsprechen der bundesgerichtlichen Praxis (vgl. Urteil 1C_440/2010 vom 8. März 2011 E. 3.4 mit Hinweis) und sind nicht zu beanstanden.
Zwar machen die Beschwerdeführer geltend, sie hätten selbst einen Nachteil erlitten, weil durch die mangelhafte Aussteckung Personen von der Beschwerdeführung abgehalten worden seien, die sie als Koalitionspartner unterstützen und ihren Anliegen grösseres Gewicht verschafft hätten. Dem ist jedoch entgegenzuhalten, dass die Erfolgsaussichten eines Rechtsmittels nicht von der Zahl der beschwerdeführenden Parteien abhängen. Entscheidend ist, dass die Beschwerdeführer die Möglichkeit hatten, sämtliche Rügen gegen das umstrittene Projekt vorzubringen und gerichtlich überprüfen zu lassen und ihnen damit das rechtliche Gehör gewährt worden ist.
2.2 Die Beschwerdeführer rügen weiter, das Verwaltungsgericht habe zu Unrecht auf den von ihnen beantragten Augenschein verzichtet; dies habe dazu geführt, dass das Verwaltungsgericht der sachverhaltlich falschen Darstellung der Beschwerdegegnerschaft gefolgt sei, insbesondere zur Abfall- und Lärmsituation in der Umgebung des geplanten Stegs und zum Genügen der Ersatzmassnahmen.
Damit erheben die Beschwerdeführer Sachverhaltsrügen. Diese (und eine allfällig daraus resultierende Pflicht zur Durchführung eines Augenscheins) sind im Zusammenhang mit den jeweiligen materiellen Rügen (betr. Abfall, Lärm und Ersatzmassnahmen) zu prüfen.
2.3 Die Beschwerdeführer machen überdies eine Verletzung der Koordinationspflicht gemäss Art. 25a des Bundesgesetzes vom 22. Juni 1979 über die Raumplanung (RPG; SR 700) geltend, weil im Feststellungsbeschluss gemäss Strassengesetz nicht auch über die enteignungsrechtlichen Fragen entschieden worden sei.
Das Verwaltungsgericht hielt dazu fest, dass sich enteignungsrechtliche Forderungen nach §§ 32 ff. AbtrG richten und nicht Gegenstand des Projektierungsverfahrens gemäss Art. 43 ff. des Zürcher Strassengesetzes vom 27. September 1981 (StrG) seien. Die Koordinationspflicht gemäss Art. 25a RPG betreffe lediglich jene Verfahren, die sich mit den baurechtlichen Bewilligungsvoraussetzungen befassten, nicht aber das Verfahren, das sich mit den enteignungsrechtlichen Folgen der Bewilligungserteilung befassten.
Die Beschwerdeführer sind grundsätzlich einverstanden, dass das Schätzungsverfahren später durchgeführt werde, beharren aber darauf, dass schon im strassenrechtlichen Verfahren zumindest über die Rechtzeitigkeit ihrer entschädigungsrechtlichen Anträge und das Vorliegen von Unfreiwilligkeit i.S.v. § 13 AbtrG entschieden werden müsse. Sie legen aber nicht dar, weshalb diese Aspekte einen so engen sachlichen Zusammenhang mit den im Projektierungsverfahren zu prüfenden Fragen aufweisen, dass darüber nicht getrennt und unabhängig voneinander entschieden werden könne (<ref-ruling> E. 5d S. 39 f.); dies ist auch nicht ersichtlich.
3. Die Beschwerdeführer rügen sodann eine offensichtlich falsche Sachverhaltsfeststellung des Verwaltungsgerichts im Zusammenhang mit der Begutachtung durch die Natur- und Heimatschutzkommission des Kantons Zürich (NHK): In E. 2.4 des angefochtenen Entscheids führe die Vorinstanz aus, dass sich die NHK am 13. Oktober 2005 positiv zum geplanten Seesteg geäussert habe. Dies sei nachweislich falsch: Das Gutachten der NHK datiere vom 20. April 2006 (Nr. 02-2006) und habe sich gegen die Stegvariante im See ausgesprochen. Das vom Verwaltungsgericht zitierte Schreiben vom 13. Oktober 2005 stamme vom Geschäftsführer des Stadtzürcher Heimatschutzes. Das Verwaltungsgericht sei mit keiner Silbe auf die Stellungnahme der NHK eingegangen, obwohl die Beschwerdeführer sich mehrfach darauf bezogen hätten. Damit habe es ein zentrales Aktenstück nicht gewürdigt.
Falsch sei auch die Feststellung des Verwaltungsgerichts, wonach das Stegprojekt nicht im Bereich eines Schutzobjektes von überkommunaler Bedeutung liege. Vielmehr sei der ganze Uferbereich des Zürichsees ein Landschaftsschutzobjekt sui generis i.S.v. § 203 Abs. 1 lit. a des Zürcher Planungs- und Baugesetzes vom 7. September 1975 (PBG).
3.1 Das Verwaltungsgericht weist in seiner Vernehmlassung darauf hin, dass die Stellungnahme der NHK vom 20. April 2006 nicht bei den Akten gelegen habe, die ihm eingereicht worden seien.
3.2 Die Stadt Zürich gibt zu Bedenken, dass sich die NHK nicht zum konkreten Projekt geäussert habe, sondern lediglich zur grundsätzlichen Frage der Wegführung. Ursprünglich hätten 3 Varianten zur Debatte gestanden: Ein Weg an Land, ein Weg auf einem dem Ufer entlang verlaufenden Steg und ein Steg im See. Während sich die NHK kritisch zur Variante "Steg im See" geäussert und sich für einen Weg am Ufer ausgesprochen habe, habe der Stadtzürcher Heimatschutz diese Variante befürwortet. Die Stadt habe sich mit Rücksicht auf die Interessen der Seeanstösser (und damit auch der Beschwerdeführer) für die Variante im See ausgesprochen. Sie habe jedoch den Bedenken der NHK bei der Ausarbeitung des Projekts Rechnung getragen. An diesem seien alle zuständigen städtischen und kantonalen Stellen beteiligt worden, insbesondere auch das kantonale Amt für Landschaft und Natur (ALN) und das kantonale Amt für Raumordnung und Vermessung (ARV). Die einbezogenen Fachleute und -behörden seien zum Ergebnis gekommen, dass das Landschaftsbild durch den Stegbau nicht beeinträchtigt und die denkmalgeschützten Bootshäuser optisch nicht abgeriegelt würden. Eine Verpflichtung zur Einholung eines Gutachtens der NHK habe nicht bestanden.
3.3 Das Bundesgericht ist an den von der Vorinstanz festgestellten Sachverhalt gebunden, soweit dieser nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 und <ref-law>). Neue Tatsachen und Beweismittel können nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Das Verwaltungsgericht hat die Stellungnahme der NHK - einer kantonalen Sachverständigenkommission - aus dem Jahr 2006 mit der in den Akten liegenden Stellungnahme des Geschäftsführers des Stadtzürcher Heimatschutzes - einer privaten Vereinigung - aus dem Jahr 2005 verwechselt. Seine Feststellung, wonach sich die NHK am 13. Oktober 2005 positiv zum geplanten Seesteg geäussert habe, ist offensichtlich falsch.
Entgegen der Auffassung der Stadt Zürich handelt es sich nicht um ein nach <ref-law> unzulässiges Novum: Bereits der Regierungsrat hatte sich im Rekursentscheid vom 17. August 2011 (E. 9b und c) ausführlich zum Gutachten der NHK geäussert. Die Beschwerdeführer durften deshalb davon ausgehen, dass dieses bei den Akten liege oder vom Verwaltungsgericht beigezogen werde. Erst das verwaltungsgerichtliche Urteil gab ihnen Anlass, eine Kopie des NHK-Gutachtens einzureichen.
Gemäss <ref-law> führt eine offensichtlich falsche Sachverhaltsfeststellung nur dann zur Aufhebung des angefochtenen Entscheids, soweit die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann. Hierfür genügt es, wenn bei korrekter Ermittlung des Sachverhalts ein anderer Entscheid in der Sache möglich wäre (MARKUS SCHOTT, Basler Kommentar zu BGG, 2. Auflage, N. 23 zu <ref-law>). Dies ist im Folgenden zu prüfen.
3.4 Die Beschwerdeführer hatten vor Verwaltungsgericht beantragt, ein neues Gutachten der NHK zum konkreten Projekt einzuholen. Das Verwaltungsgericht wies diesen Antrag ab, weil sich die NHK bereits mit Stellungnahme vom 13. Oktober 2005 geäussert und die Erstellung eines Seestegs am geplanten Standort befürwortet habe. Ein neues Gutachten müsse daher nur eingeholt werden, wenn begründete Zweifel an der richtigen und unabhängigen Beurteilung der Sachfrage bestünden oder wenn das frühere Gutachten mit Ablauf der Zeit und zufolge veränderter Verhältnisse an Aktualität eingebüsst hätte; beides sei vorliegend nicht der Fall. Zudem liege das Projekt nicht im Bereich eines Schutzobjekts von überkommunaler Bedeutung, sodass gemäss § 3 Abs. 1 lit. d der Verordnung vom 12. Januar 2005 über die Sachverständigenkommissionen gemäss § 216 PBG keine gesetzliche Verpflichtung bestehe, eine Stellungnahme der NHK einzuholen.
Des Weiteren erwähnte das Verwaltungsgericht die angeblich positive Stellungnahme der NHK im Zusammenhang mit den Rügen der Beschwerdeführer, wonach der geplante Seesteg überdimensioniert sei, das Landschaftsbild beeinträchtige und die Bucht und die Badeanstalt unter Verletzung von Denkmalschutzvorschriften abriegle (E. 4.4 des angefochtenen Entscheids).
Hätte das Verwaltungsgericht die negative Stellungnahme der NHK zur Lage des Stegs im See gekannt, kann nicht ausgeschlossen werden, dass es dem Antrag auf Einholung eines erneuten Gutachtens entsprochen hätte:
3.4.1 Zwar ist mit den Vorinstanzen davon auszugehen, dass die Anhörung der NHK nicht zwingend geboten, sondern fakultativ war, weil es sich beim Zürichsee im vorliegenden Bereich nicht um ein überkommunales Schutzobjekt handelt (vgl. § 3 Abs. 1 lit. d und Abs. 2 der Verordnung vom 12. Januar 2005 über die Sachverständigenkommissionen gemäss § 216 PBG):
Die Stadt Zürich hat diesen Seeteil als "Landschaftsschutzobjekt Zürichsee" (KSO-32) ausgewiesen, d.h. als kommunales Schutzobjekt. Es ist auch nicht ersichtlich, dass eine überkommunale Unterschutzstellung gestützt auf § 203 Abs. 1 lit. a PBG geboten wäre: Nach dieser Bestimmung sind "im Wesentlichen unverdorbene Natur- und Kulturlandschaften sowie entsprechende Gewässer, samt Ufer und Bewachsung" Schutzobjekte. Wie das BAFU in seiner Vernehmlassung darlegt, ist das vorliegende Gebiet am Ufer vollständig bebaut; es handelt sich nicht um eine "unverdorbene Naturlandschaft", sondern um eine Siedlungslandschaft, die am Ufer von privaten Gebäuden und Gärten geprägt wird.
3.4.2 Allerdings kommt auch einer fakultativen Stellungnahme der NHK als unabhängiger kantonaler Sachverständigenkommission besonderes Gewicht zu.
Die NHK kam 2006 zum Schluss, dass eine weitere Besetzung des Seespiegels nicht wünschenswert sei, obwohl sich die Auswirkungen aus rein ökologischer Sicht in Grenzen hielten. Die geplante Seepromenade werde im See als Baukörper erscheinen, der eine Hafensituation simulieren werde, ohne eine eigentliche Mehrnutzung, ausser jener der Promenade, zu ermöglichen. Diese Massnahme besetze die Seelandschaft mit einem neuen Bild, dessen Dimensionen der Massstäblichkeit des Eingriffs nicht entsprächen. Zudem müsse die Funktionalität der im Perimeter bestehenden Bootshäuser erhalten werden. Die NHK empfahl, die Variante "Weg am Ufer" als vernünftige Lösung erneut zu überprüfen. Bereits die Dimensionen des avisierten Perimeters zeigten an, wie gross eigentlich das Vorhaben sei, eine Passerelle in den See zu setzen: Es werde ein neuer Seebeckenbereich geboren, der zwei intensiv genutzte Freiräume verbinde. Folgerichtig sei deshalb eine detaillierte Nutzungsstrategie zwingender Bestandteil eines Wettbewerbsprogramms.
3.4.3 Die Stadt und der Regierungsrat gingen davon aus, dass den Bedenken der NHK durch die konkrete Ausgestaltung des Stegs Rechnung getragen worden sei: Durch die gewählte schlanke Konstruktion, die weitgehende Lichtdurchlässigkeit der Geländer und die erhebliche Entfernung von Seeufer (rund 100 m) werde der Seesteg vom Ufer aus verhältnismässig leicht und filigran in Erscheinung treten; die Beeinträchtigung des freien Blicks auf den See werde damit auf ein vertretbares Mass verringert. Der Eindruck einer eigentlichen Hafensituation entstehe jedenfalls nicht und die Besetzung des Seespiegels scheine vertretbar. Um die Durchfahrt für Boote zu gewährleisten, solle der Steg mit einem leichten Längsgefälle von höchstens 1 % ausgeführt werden, sodass in einem Teilbereich eine Mindestdurchfahrtshöhe von 2 m gegeben sei; damit werde die Funktionalität der Bootshäuser erhalten. Die Beeinträchtigung des Landschaftsbildes halte sich infolge der ausgeprägt linearhorizontalen Komponente des Steges in Grenzen.
3.4.4 Diesen Ausführungen lässt sich entnehmen, dass das zu bewilligende Projekt sich wesentlich von dem Vorprojekt unterscheidet, das Grundlage des Gutachtens der NHK im Jahr 2006 war. Insofern liesse sich die Auffassung vertreten, dass eine Änderung der Situation vorliegt, welches die Einholung eines neuen Gutachtens der NHK rechtfertigen könnte.
Ist damit der Antrag der Beschwerdeführer auf Einholung eines erneuten Gutachtens der NHK nicht von vornherein aussichtslos, haben diese nach <ref-law> Anspruch darauf, dass das Verwaltungsgericht gestützt auf einen korrekten Sachverhalt über ihren Beweisantrag entscheidet. Sollte ihrem Beweisantrag stattgegeben werden, würde der Ausgang des Verfahrens von den Schlussfolgerungen des neuen NHK-Gutachtens beeinflusst werden. Es kann jedenfalls nicht ausgeschlossen werden, dass das Verwaltungsgericht gestützt auf ein neues Gutachten der NHK ganz oder teilweise (z.B. hinsichtlich der beantragten Auflagen) zu einem anderen Ergebnis gelangen könnte.
4. Nach dem Gesagten ist die Beschwerde gutzuheissen, der angefochtene Entscheid aufzuheben und die Sache an das Verwaltungsgericht zurückzuweisen.
Dieses wird zunächst über den Antrag auf Einholung eines neuen Gutachtens der NHK entscheiden müssen. Gibt es dem Antrag statt, wird es prüfen müssen, ob das streitige Projekt unter Berücksichtigung des neuen Gutachtens bewilligungsfähig ist. Lehnt es den Beweisantrag ab, wird es dies neu begründen müssen. Diesfalls wird das Gericht selbst überprüfen müssen, ob die Projektierung allen Bedenken der NHK gegen das Vorhaben ausreichend Rechnung trägt.
Es wird Sache des Verwaltungsgerichts sein zu entscheiden, ob es hierfür auf einen Augenschein angewiesen ist oder nicht; eine diesbezügliche Anordnung rechtfertigt sich nicht.
Abzuweisen ist auch der Antrag der Beschwerdeführer, wonach für den Fall der Rückweisung die Einholung einer Umweltverträglichkeitsprüfung (UVP) anzuordnen sei. Hierfür kann auf die zutreffenden Ausführungen im angefochtenen Entscheid (E. 2.3) verwiesen werden.
Damit obsiegen die Beschwerdeführer überwiegend. Ihnen ist eine Parteientschädigung zuzusprechen (<ref-law>) und es sind keine Kosten zu erheben (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Zürich, 3. Abteilung, vom 21. Dezember 2011 aufgehoben. Die Sache wird zu neuer Beurteilung im Sinne der Erwägungen an das Verwaltungsgericht zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
2. Es werden keine Kosten erhoben.
3. Die Stadt Zürich hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 4'000.-- zu entschädigen.
4. Dieses Urteil wird den Beschwerdeführern, der Stadt Zürich, dem Regierungsrat des Kantons Zürich, dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, 3. Kammer, dem Bundesamt für Raumentwicklung und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 7. September 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber