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 an das Bundesgericht 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 (Art. 34 Abs. 1 BV) sowie die Verletzung des Anspruchs auf rechtliches Gehör und Begründung des Entscheids (Art. 29 Abs. 2 BV). 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. F. Mit Urteil 1C_451/2007 vom 17. März 2008 erkannte das Bundesgericht, das Verwaltungsgericht des Kanton Zürich sei zur Behandlung der Beschwerde zuständig, weshalb es die Angelegenheit an dieses Gericht zur Behandlung überwies. Das Bundesgericht führte aus, das kantonale Recht sehe als letzte Rechtsmittelinstanz in kantonalen und kommunalen Stimmrechtsangelegenheiten die Beschwerde an das Verwaltungsgericht vor. Der angefochtene Entscheid sei somit nicht letztinstanzlich. Die Beschwerdeführer hätten sich mit der Einreichung ihrer Beschwerde beim Bundesgericht auf eine fehlerhafte Rechtsmittelbelehrung des Regierungsrats verlassen, was für sie keinen Nachteil zur Folge haben dürfe. Somit sei die Sache an das Verwaltungsgericht zu überweisen. G. Mit Beschluss vom 16. April 2008 trat das Verwaltungsgericht auf die Beschwerde nicht ein. Es erwog im Wesentlichen, die regierungsrätliche Verordnung, auf welche das Bundesgericht die Zuständigkeit des Verwaltungsgerichts abgestützt habe, habe lediglich die Klarstellung bezweckt, dass das Verwaltungsgericht nach Inkrafttreten des Bundesgerichtsgesetzes am 1. Januar 2007 in denjenigen Fällen zuständig bleibe, in welchen früher die Verwaltungsgerichtsbeschwerde an das Bundesgericht erhoben werden konnte und neu eine ordentliche Beschwerde im Sinne der Art. 72 ff. BGG gegeben sei. Kantonale und kommunale Stimmrechtsangelegenheiten unterlägen nach der bundesgerichtlichen Rechtsprechung zum BGG neu zwar grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten nach Art. 82 lit. c BGG, doch sei vor Inkrafttreten des Bundesgerichtsgesetzes nur die staatsrechtliche Beschwerde (Stimmrechtsbeschwerde) zulässig gewesen. Die regierungsrätliche Verordnung über die Anpassung des kantonalen Rechts an das Bundesgerichtsgesetz vom 29. November 2006 (VO BGG, OS 61,480) begründe somit nicht die Zulässigkeit einer Stimmrechtsbeschwerde beim Verwaltungsgericht. Dies führte das Verwaltungsgericht dazu, auf die Beschwerde nicht einzutreten. Um die Beschwerdeführer nicht der Gefahr eines Rechtsverlusts auszusetzen, leitete das Verwaltungsgericht die Angelegenheit an das Bundesgericht zurück. H. Mit Schreiben vom 28. April 2008 teilte das Bundesgericht den Beschwerdeführern mit, dass das Gericht in Aussicht nehme, die Behandlung ihrer Beschwerde vom 14. Dezember 2007 unter der neuen Geschäftsnummer 1C_183/2008 weiterzuführen. 