Sachverhalt: A. Am 28. November 2004 fand in der Stadt Bern die im Proporzverfahren durchgeführte Wahl des Gemeinderates (Exekutive) für die Amtsdauer 2005 - 2008 statt. Gemäss Protokoll der Stadtkanzlei erzielte die RotGrünMitte-Liste aufgrund der Gesamtzahl der Listenstimmen drei Gemeinderatssitze. Auf dieser Liste belegte Regula Rytz mit 20'606 Stimmen den dritten Rang; sie hatte 19 Stimmen mehr erhalten als Alec von Graffenried mit 20'587 Stimmen auf dem vierten Rang. Demnach war Regula Rytz in den Gemeinderat gewählt, während Alec von Graffenried ausschied. Der Gemeinderat nahm am 1. Dezember 2004 vom Bericht der Stadtkanzlei über die Gemeinderatswahl Kenntnis und wies gleichzeitig das Begehren der Grünen Freien Liste (GFL) um Nachzählung ab. Demnach galt Regula Rytz als in den Gemeinderat gewählt. B. Sebastian Bentz führte in der Folge Gemeindebeschwerde bei der Regierungsstatthalterin und verlangte eine Nachzählung der Wahlzettel und eine Auswertung einzelner Kategorien von Wahlzetteln. Mit separater Eingabe erhoben Bruno Studer, Martin Kindler und Marcel Studer Wahlbeschwerde und beantragten ebenfalls die Nachzählung der für Regula Rytz bzw. Alec von Graffenried abgegebenen sowie der ungültig erklärten Stimmen. Die Justiz-, Gemeinde- und Kirchendirektion des Kantons Bern wies am 9. Dezember 2004 ein Ablehnungsbegehren gegen die Regierungsstatthalterin ab. Die Regierungsstatthalterin entzog der Beschwerde die aufschiebende Wirkung, führte eine Untersuchung und wies die Beschwerden am 10. Januar 2005 ab. Zur Begründung führte sie aus, der Gemeinderat habe das Reglement der Stadt Bern über die politischen Rechte korrekt angewendet, das Vorliegen einer geringen Stimmendifferenz begründe für sich allein keinen Anspruch auf Nachzählung und es lägen - nach Abklärung der Verhältnisse im Zählkreis 5 - keine Hinweise auf Unregelmässigkeiten vor, sodass die Knappheit des Resultates keine Zweifel an der Richtigkeit der Ermittlungen des Wahlergebnisses zu begründen vermöge. C. Bruno Studer, Martin Kindler und Marcel Studer fochten diesen Entscheid beim Regierungsrat des Kantons Bern an. Mit separater Eingabe erhob auch Sebastian Bentz Beschwerde. Sie machten im Wesentlichen geltend, in Anbetracht notorischer Zählfehler bestehe bei knappem Wahlausgang aufgrund von Art. 34 Abs. 2 BV ein Anspruch auf Nachzählung. Im Übrigen bemängelten sie das Verfahren der Auszählung und rügten teilweise Verletzungen des rechtlichen Gehörs. Das Rechtsamt der Justiz-, Gemeinde- und Kirchendirektion entzog der Beschwerde am 9. Februar 2005 die aufschiebende Wirkung und nahm verschiedene Instruktionsmassnahmen vor. Mit Entscheid vom 20. April 2005 wies der Regierungsrat die Beschwerden ab. Er hielt fest, dass ein knappes Resultat für sich allein genommen keinen Anspruch auf eine Nachzählung begründe. Gewisse - ausdrücklich festgehaltene - Mängel des Auszählungsverfahrens hätten sich auf das Wahlresultat und insbesondere auf den Stimmenunterschied zwischen Regula Rytz und Alec von Graffenried nicht ausgewirkt. D. Gegen diesen Entscheid des Regierungsrates haben Bruno Studer, Martin Kindler und Marcel Studer beim Bundesgericht am 20. Mai 2005 staatsrechtliche Beschwerde wegen Verletzung von Art. 34 BV erhoben. Sie machen im Wesentlichen geltend, angesichts des knappen Wahlresultats und konkreter Anhaltspunkte für fehlerhafte bzw. gesetzwidrige Auszählung einen Anspruch auf Nachzählung zu haben. Der Gemeinderat stellt mit seiner Vernehmlassung den Antrag, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Justiz-, Gemeinde- und Kirchendirektion beantragt für den Regierungsrat die Abweisung der Beschwerde.