Sachverhalt:
A. Der Gemeinderat Zürich genehmigte am 16. Dezember 2006 den Entwurf zum Budget der laufenden Rechnung und der Investitionsrechnung für das Jahr 2007 und lehnte dabei einen in der Budgetdebatte gestellten Antrag, die Ausgaben für die Sanierung der Hardbrücke nicht zu genehmigen, ab. Mit Beschlüssen vom 20. Dezember 2006 setzte der Stadtrat von Zürich das Instandsetzungsprojekt Hardbrücke fest und bewilligte als neue Ausgabe einen Objektkredit von 1.85 Mio. Franken für den Bau eines kombinierten Rad-/Gehwegs zwischen Hardplatz und Bahnhof Hardbrücke sowie gebundene Ausgaben von insgesamt 88.5 Mio. Franken für die Instandsetzung der Hardbrücke. Diese Finanzbeschlüsse wurden keinem Referendum unterstellt.
B. Niklaus Scherr, Bastien Giroud, Richard Rabelbauer, Robert Schönbächler und Markus Zimmermann gelangten gegen die Beschlüsse des Stadtrats mit Stimmrechtsrekurs an den Bezirksrat Zürich, der das Rechtsmittel am 5. Juli 2007 abwies und den für die Instandsetzung der Hardbrücke bewilligten Betrag als gebundene Ausgaben bezeichnete. Einen gegen den Entscheid des Bezirksrats erhobenen Rekurs wies der Regierungsrat des Kantons Zürich mit Beschluss vom 7. November 2007 ab, soweit er darauf eintreten konnte.
C. Mit als Stimmrechtsbeschwerde bezeichneter Eingabe vom 14. Dezember 2007 beantragen die im kantonalen Verfahren unterlegenen Rekurrenten im Hauptantrag, der Entscheid des Regierungsrats vom 7. November 2007 sei aufzuheben und die Sache sei zur Fortsetzung des Verfahrens an die Vorinstanzen zurückzuweisen. In einem ersten Eventualantrag verlangen sie im Wesentlichen, der Objektkredit und die Bewilligung gebundener Ausgaben gemäss dem Beschluss des Stadtrats sei aufzuheben und es sei festzustellen, dass der gesamte Kreditbetrag von 90.35 Mio. Franken nach Art. 10 lit. d der Gemeindeordnung der Stadt Zürich vom 26. April 1970 (GO) dem obligatorischen Referendum unterliege. In einem zweiten Eventualantrag ersuchen sie um die Feststellung, ein Anteil des gesamten Kreditbetrags von über 2 Mio. Franken stelle keine gebundene Ausgabe dar und unterliege deshalb dem fakultativen, allenfalls dem obligatorischen Referendum. Der Stadtrat sei anzuweisen, dem Gemeinderat entsprechend Antrag zu stellen.
Die Beschwerdeführer berufen sich auf die Abgrenzung der gebundenen von den neuen Ausgaben gemäss Art. 10 ff. GO. Sie rügen die Verletzung ihres Stimmrechts sowie die Verletzung des Anspruchs auf rechtliches Gehör und Begründung des Entscheids (<ref-law>).
D. Der Stadtrat Zürich und der Regierungsrat des Kantons Zürich schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten sei.
E. Mit Präsidialverfügung vom 18. Januar 2007 wurde ein Gesuch der Beschwerdeführer um aufschiebende Wirkung abgewiesen.

Erwägungen:
1. 1.1 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> kann die Verletzung politischer Rechte geltend gemacht werden. Dazu zählt die Rüge, ein Finanzbeschluss sei zu Unrecht nicht dem Referendum unterstellt worden. Zur Beschwerde ist gemäss <ref-law> legitimiert, wer in der betreffenden Angelegenheit stimmberechtigt ist. Dieses Erfordernis erfüllen die Beschwerdeführer. Die Beschwerdefrist von <ref-law> ist eingehalten.
1.2 Beschwerden betreffend Volksabstimmungen in kantonalen Angelegenheiten sind gegen Akte letzter kantonaler Instanzen zulässig (<ref-law>). Die Kantone sehen gegen behördliche Akte, welche die politischen Rechte verletzen können, ein Rechtsmittel vor (<ref-law>). Diese Pflicht erstreckt sich nicht auf Akte des Parlaments oder der Regierung (<ref-law>).
Vor dem Hintergrund von <ref-law> und der Zielsetzungen des Bundesgerichtsgesetzes hat das Bundesgericht entschieden, dass die Kantone als Rechtsmittelinstanz im Sinne von <ref-law> eine gerichtliche Behörde einsetzen müssen. Diese Pflicht besteht sowohl in kantonalen als auch in kommunalen Stimmrechtsangelegenheiten (Urteile des Bundesgerichts 1P.338/2006 und 1P.582/2006 vom 12. Februar 2007, E. 3.10, ZBl 108/2007 S. 313; 1C_185/2007 vom 6. November 2007 E. 1.2 mit Hinweisen).
1.2.1 Die Kantone sind gemäss <ref-law> verpflichtet, innert zwei Jahren seit Inkrafttreten des Bundesgerichtsgesetzes die erforderlichen Ausführungsbestimmungen über die Zuständigkeit, die Organisation und das Verfahren der bundesgerichtlichen Vorinstanzen zu erlassen. § 43 Abs. 1 lit. a des Verwaltungsrechtspflegegesetzes des Kantons Zürich vom 24. Mai 1959 (VRG) schliesst die Beschwerde an das kantonale Verwaltungsgericht auf dem Gebiet von Wahlen und Abstimmungen grundsätzlich aus (vgl. Alfred Kölz/Jürg Bosshart/Martin Röhl, Kommentar zum Verwaltungsrechtspflegegesetz des Kantons Zürich, 2. Auflage, Zürich 1999, § 43 N. 5). § 43 Abs. 2 VRG sieht jedoch vor, dass die Beschwerde an das Verwaltungsgericht auch in den Fällen von Abs. 1 zulässig ist, soweit die Verwaltungsgerichtsbeschwerde an das Bundesgericht offensteht oder wenn es sich um eine Angelegenheit gemäss Art. 6 Ziff. 1 EMRK handelt. Nach § 5 der Verordnung des Regierungsrats des Kantons Zürich vom 29. November 2006 über die Anpassung des kantonalen Rechts an das Bundesgerichtsgesetz (VO BGG, OS 61,480) ist unter Verwaltungsgerichtsbeschwerde an das Bundesgericht die ordentliche Beschwerde an das Bundesgericht zu verstehen. Diese genannte Verordnung des Regierungsrats trat gleichzeitig wie das Bundesgerichtsgesetz am 1. Januar 2007 in Kraft. Damit hat der Regierungsrat von der ihm in <ref-law> in Verbindung mit Art. 67 der Verfassung des Kantons Zürich vom 27. Februar 2005 (KV/ZH) eingeräumten Kompetenz Gebrauch gemacht, die Ausführungsbestimmungen in die Form nicht referendumspflichtiger Erlasse zu kleiden, sofern dies zur Einhaltung der Fristen nach den Absätzen 1-3 von <ref-law> notwendig ist. Der Regierungsrat hat in § 5 VO BGG keine Vorbehalte in Bezug auf die früher nicht der Verwaltungsgerichtsbeschwerde an das Bundesgericht unterlegenen kantonalen Rechtsmittelentscheide und Stimmrechtsangelegenheiten angebracht (Art. 82 lit. a und c BGG). Dass er die zweijährige Übergangsfrist gemäss <ref-law> nicht ausgeschöpft hat, ist nicht zu beanstanden.
1.2.2 In der vorliegenden Angelegenheit sind kommunale Kreditbeschlüsse umstritten, welche wie erwähnt nach den Vorschriften des Bundesgerichtsgesetzes der ordentlichen Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht unterliegen, nachdem ein kantonal letztinstanzlicher Rechtsmittelentscheid vorliegt. Gemäss § 43 Abs. 1 lit. a und Abs. 2 VRG in Verbindung mit § 5 VO BGG ist in solchen Fällen deshalb die Beschwerde an das kantonale Verwaltungsgericht zulässig. Das Verwaltungsgericht ist als einzige richterliche Behörde zur freien Sachverhaltsprüfung und zur Rechtsanwendung von Amtes wegen sowie zur Wahrung der Einheit des Verfahrens verpflichtet (Art. 110 f. BGG). Es ergibt sich, dass mit dem angefochtenen Entscheid des Regierungsrats kein kantonal letztinstanzlicher Entscheid im Sinne von <ref-law> vorliegt.
1.3 Das Bundesgericht verzichtet in konstanter Praxis auf das Erfordernis der Erschöpfung des kantonalen Instanzenzuges, wenn an der Zulässigkeit eines Rechtsmittels ernsthafte Zweifel bestehen (<ref-ruling> E. 1.5 S. 94 mit Hinweisen). Solche Zweifel bestehen nach den vorstehenden Erwägungen nicht.
1.3.1 Unter dem Gesichtspunkt von Treu und Glauben (<ref-law>) ist zu beachten, dass der angefochtene Entscheid eine Rechtsmittelbelehrung enthält, nach welcher gegen den Regierungsratsentscheid beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben werden könne. Aus einer unrichtigen Rechtsmittelbelehrung dürfen den Parteien keine Nachteile erwachsen (<ref-law>; Art. 18 Abs. 2 KV/ZH; <ref-ruling> E. 1.6 S. 96). Wird aufgrund einer unrichtigen Belehrung ein falsches Rechtsmittel ergriffen, kann die Sache daher von Amtes wegen an die zuständige Instanz überwiesen werden (<ref-ruling> E. 8b S. 239 f. mit Hinweisen). Allerdings geniesst nur Vertrauensschutz, wer die Unrichtigkeit der Rechtsmittelbelehrung nicht kennt und sie auch bei gebührender Aufmerksamkeit nicht hätte erkennen können. Rechtsuchende geniessen keinen Vertrauensschutz, wenn der Mangel für sie bzw. ihren Rechtsvertreter allein schon durch Konsultierung der massgeblichen Verfahrensbestimmung ersichtlich ist. Dagegen wird nicht verlangt, dass neben den Gesetzestexten auch noch die einschlägige Rechtsprechung oder Literatur nachgeschlagen wird (vgl. <ref-ruling> E. 1a/aa S. 258; <ref-ruling> E. 3a S. 125, 421 E. 2a, je mit weiteren Hinweisen; Urteil des Bundesgerichts 1P.653/1997 vom 13. Februar 1998, publ. in ZBl 100/1999 S. 80 ff.).
1.3.2 Der angefochtene Beschluss enthält eine unrichtige Rechtsmittelbelehrung. Es war für die nicht anwaltlich vertretenen Beschwerdeführer nicht ohne Weiteres erkennbar, dass das Verwaltungsgericht als letzte kantonale Instanz zur Beurteilung der vorliegenden Stimmrechtsangelegenheit zuständig ist, da dies nicht dem Wortlaut von § 5 VO BGG und § 43 Abs. 2 VRG entnommen werden kann, sondern nur im Zusammenhang mit den Neuerungen, die sich aus der Beschwerde in öffentlich-rechtlichen Angelegenheiten ergeben, ersichtlich ist. Unter diesen Umständen ist die Beschwerde dem Verwaltungsgericht des Kantons Zürich zur Behandlung zu überweisen (vgl. <ref-ruling> E. 1.6 S. 96; <ref-ruling> E. 5 S. 320 mit Hinweis).
2. Zusammenfassend ergibt sich, dass die vorliegende Beschwerde mangels Erschöpfung des kantonalen Instanzenzugs ausgeschlossen ist. Die Beschwerde wird dem Verwaltungsgericht des Kantons Zürich zur Behandlung überwiesen. Es werden keine Gerichtskosten erhoben (Art. 66 Abs. 1 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Eingabe der Beschwerdeführer vom 14. Dezember 2007 wird dem Verwaltungsgericht des Kantons Zürich zur Behandlung überwiesen.
2. Das bundesgerichtliche Verfahren 1C_451/2007 wird als gegenstandslos geworden vom Geschäftsverzeichnis abgeschrieben.
3. Es werden keine Gerichtskosten erhoben.
4. Dieses Urteil wird den Beschwerdeführern, der Stadt Zürich und dem Bezirksrat Zürich sowie dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 17. März 2008
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Haag