Sachverhalt: A. Die Gemeindeversammlung der Einwohnergemeinde Grindelwald beschloss am 7. Dezember 2001 ein neues Gemeinwerkreglement. Gegen dieses Reglement liessen A._ und B._, beide Grundeigentümer in Grindelwald, vertreten durch Advokat C._, Gemeindebeschwerde beim Regierungsstatthalter von Interlaken einreichen, welcher das Rechtsmittel mit Entscheid vom 8. August 2002 im Wesentlichen abwies. Dagegen erhoben A._ und B._ Beschwerde beim Regierungsrat des Kantons Bern. Dieser kassierte den angefochtenen Entscheid des Regierungsstatthalters am 19. März 2003 von Amtes wegen und leitete die Gemeindebeschwerden weiter an das kantonale Amt für Gemeinden und Raumordnung zur Behandlung als Einsprachen im Rahmen des für kommunale Reglemente wie das streitige Gemeinwerkreglement erforderlichen und daher nachzuholenden kantonalen Genehmigungsverfahrens. B. Mit Verfügung vom 26. Juni 2003 genehmigte das Amt für Gemeinden und Raumordnung des Kantons Bern das Gemeinwerkreglement vom 7. Dezember 2001 der Einwohnergemeinde Grindelwald und wies die Einsprachen von A._ und B._ ab. Dagegen erhoben A._, B._ und neu auch C._ in eigenem Namen Beschwerde an die Justiz-, Gemeinde- und Kirchendirektion des Kantons Bern. Diese trat mit Entscheid vom 16. April 2004 auf die Beschwerde, soweit sie von C._ erhoben wurde, nicht ein und wies sie im Übrigen ab. C. Mit Eingabe vom 17. Mai 2004 erheben A._, B._ sowie C._ beim Bundesgericht staatsrechtliche Beschwerde mit dem Antrag, der Entscheid der Justiz-, Gemeinde- und Kirchendirektion vom 16. April 2004 sei aufzuheben. Sodann wird auch um Aufhebung des Beschlusses der Einwohnergemeinde Grindelwald vom 7. Dezember 2001 "betreffend Inkraftsetzung des Gemeinwerkreglementes 2001" ersucht. Eventualiter seien die Art. 1, 2, 3 lit. a und b, Art. 4 Abs. 1 und Abs. 4, Art. 5 Abs. 1, Art. 10 Abs. 2, Art. 11 Abs. 2 und Art. 13 des Gemeinwerkreglementes aufzuheben. Die Einwohnergemeinde Grindelwald sowie die Justiz-, Gemeinde- und Kirchendirektion des Kantons Bern schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten sei.