Sachverhalt: A. An der Bürgerversammlung der politischen Gemeinde Rheineck vom 21. März 2005 lehnte die Bürgerschaft entgegen den Anträgen ihres Einbürgerungsrates zwölf in den Jahren 2003 und 2004 eingereichte Einbürgerungsgesuche ab. Aufgrund einer dagegen von einer Stimmbürgerin erhobenen Beschwerde hob das Departement des Innern des Kantons St. Gallen die ablehnenden Einbürgerungsbeschlüsse mit Entscheid vom 23. August 2005 auf. Auf Beschwerde der politischen Gemeinde Rheineck hin wies das Verwaltungsgericht des Kantons St. Gallen am 6. Dezember 2005 die Angelegenheit zur Beteiligung der Gesuchsteller am Verfahren an das Departement zurück. Dieses holte daraufhin die bis anhin unterlassene Verfahrensbeteiligung der betroffenen Gesuchsteller nach. Mit Entscheiden vom 27. April 2006 hob es die ablehnenden Einbürgerungsbeschlüsse auf und wies die politische Gemeinde Rheineck an, die Einbürgerungsgesuche der nächsten Bürgerversammlung vorzulegen, soweit die Gesuchsteller die Einbürgerungsvoraussetzungen noch erfüllten. Die meisten Gesuchstellerinnen und Gesuchsteller hielten an ihrem Einbürgerungsgesuch fest. Sie wurden vom Einbürgerungsrat nochmals geprüft und wiederum positiv beurteilt. Dementsprechend beantragte der Einbürgerungsrat der Bürgerschaft an der Bürgerversammlung vom 19. März 2007, unter anderem den verbliebenen zehn Einbürgerungsvorlagen, welche ein zweites Mal zu beurteilen waren, zuzustimmen. Mehrere Personen nutzten an der Bürgerversammlung die Möglichkeit, die Einbürgerungen zu diskutieren. Dabei fiel die Diskussion nicht bei allen Vorlagen gleich ausführlich aus. Teilweise erfolgte überhaupt keine Wortmeldung. Die zehn Einbürgerungsgesuche wurden von der Bürgerversammlung wiederum abgelehnt. B. Gegen die Ablehnung ihrer Einbürgerungsgesuche gelangten unter anderem A._, die Eheleute B._ (mit Sohn E._), C._ und D._ (mit den Kindern F._, G._ und H._) mit Beschwerde an das Departement des Innern mit den Anträgen: "1. Es seien die ablehnenden Einbürgerungsbeschlüsse der Bürgerversammlung Rheineck vom 19. März 2007 aufzuheben. 2. Den Einbürgerungsgesuchen der Beschwerdeführer und Beschwerdeführerinnen sei zu entsprechen und es sei ihnen das Gemeindebürgerrecht von Rheineck zu erteilen." Zur Begründung der Beschwerde wurde insbesondere dargelegt, die Bürgerschaft habe mit ihrem Vorgehen am 19. März 2007 klar zum Ausdruck gebracht, dass sie nicht gewillt sei, Einbürgerungsentscheide in Übereinstimmung mit der geltenden Rechtsprechung vorzunehmen. Es sei deshalb unwahrscheinlich, dass ein drittes Verfahren zu einem anderen Ergebnis führen werde. Zur Vermeidung eines prozessualen Leerlaufs sei es somit notwendig, dass das Departement in der Sache selbst entscheide. Das Departement hiess die Beschwerden mit Entscheid vom 2. Juni 2008 teilweise gut und hob die ablehnenden Einbürgerungsbeschlüsse vom 19. März 2007 betreffend A._, die Eheleute B._ (mit Sohn E._), C._ und D._ (mit den Kindern F._, G._ und H._) auf. Es hielt fest, dass ein Teil der umstrittenen Einbürgerungsvorlagen diskussionslos abgelehnt worden sei. Eines der betroffenen Einbürgerungsgesuche sei trotz unterstützendem Votum und ein anderes gestützt auf die Religionszugehörigkeit abgewiesen worden. Eine weitere Absage sei nicht individuell begründet worden. Das Departement wies die Angelegenheit an die politische Gemeinde Rheineck zurück, damit der Einbürgerungsrat die Einbürgerungsvorlagen der Bürgerschaft an der nächsten Bürgerversammlung vorlegen könne, sofern die betroffenen Personen dannzumal die Einbürgerungsvoraussetzungen erfüllten (Dispositiv Ziff. 1 a-g des Entscheids). Soweit die Beschwerdeführer die Erteilung des Gemeinde- und Ortsbürgerrechts durch die Beschwerdeinstanz beantragt hatten, wies das Departement die Beschwerde ab (Dispositiv Ziff. 2 des Entscheids). Es wies die Gemeinde zudem darauf hin, dass bei einer erneut ungenügend begründeten Ablehnung der Vorlagen die Erteilung des Gemeinde- und Ortsbürgerrechts aufsichtsrechtlich angeordnet werden könnte (Dispositiv Ziff. 3 des Entscheids). C. In ihrer Beschwerde an das Verwaltungsgericht des Kantons St. Gallen beantragten A._, die Eheleute B._ (mit Sohn E._), C._ und D._ (mit den Kindern F._, G._ und H._) insbesondere, Ziff. 2 des Entscheids des Departements sei aufzuheben und ihnen sei das Gemeindebürgerrecht von Rheineck zu erteilen. Eventuell sei das Departement anzuweisen, ihren Gesuchen zu entsprechen und ihnen das Bürgerrecht zu erteilen. Mit Urteil vom 14. Oktober 2008 trat das Verwaltungsgericht auf die Beschwerde gegen Ziff. 2 des Entscheids des Departements des Innern vom 2. Juni 2008 nicht ein. Es begründete seinen Entscheid damit, dass der Verzicht auf die sofortige aufsichtsrechtliche Erteilung des Bürgerrechts nicht als Verfügung gelte, wenn die Rechtsmittelinstanz die Gesuche zur Behandlung an das gesetzlich zuständige Organ überweise. Die vorliegende Verweigerung der aufsichtsrechtlichen Erteilung des Bürgerrechts sei ein Entscheid im Rahmen der Staatsaufsicht. Dagegen sei die Beschwerde gestützt auf Art. 59bis Abs. 2 lit. a Ziff. 1 des kantonalen Verwaltungsrechtspflegegesetzes vom 16. Mai 1965 (VRP/SG; sGS 951.1) nicht zulässig, bevor die am 1. Januar 2009 ablaufende Übergangsfrist gemäss Art. 130 Abs. 3 BGG verstrichen sei. Erst ab diesem Datum hätten die Kantone die Rechtsweggarantie gemäss Art. 29a BV zu beachten und den Rechtsschutz durch ein oberes kantonales Gericht zu gewährleisten (Art. 86 Abs. 2 BGG). D. Mit Verfassungsbeschwerde vom 20. November 2008 beantragen A._, die Eheleute B._ (mit Sohn E._), C._ und D._ (mit den Kindern F._, G._ und H._) im Wesentlichen, der Nichteintretensentscheid des Verwaltungsgerichts sei aufzuheben und ihnen sei das Bürgerrecht der Gemeinde Rheineck zu erteilen. Eventuell sei die Angelegenheit zur Neubeurteilung bzw. zur materiellen Entscheidung an die Vorinstanz zurückzuweisen. Die Beschwerdeführer berufen sich auf die Menschenwürde (Art. 7 BV), das Diskriminierungsverbot (Art. 8 Abs. 2 BV), die Begründungspflicht (Art. 29 Abs. 2 BV), das Willkürverbot (Art. 9 BV) sowie die Bindung der staatlichen Organe an die Grundrechte (Art. 35 Abs. 2 BV). Zudem machen sie Rechtsverzögerung (Art. 29 Abs. 1 BV) und eine Verletzung der Art. 8 und 13 EMRK geltend. Sie bringen vor, sie hätten nach zwei verfassungswidrigen Beschlüssen der Bürgerversammlung und mehreren zu ihren Gunsten lautenden Beschwerdeentscheiden des Departements und des Verwaltungsgerichts einen Anspruch auf die Herstellung des rechtmässigen Zustands durch die Rechtsmittelinstanz. Eine nochmalige Rückweisung der Sache an die Gemeindebehörden missachte die Pflicht der Rechtsmittelinstanzen zur Rechtsgewährleistung und verfassungskonformen Beurteilung innert angemessener Frist. E. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Mangels eines Rechtsanspruchs auf eine Einbürgerung hätten die Beschwerdeführer kein rechtlich geschütztes Interesse an der Aufhebung des angefochtenen Entscheids (Art. 115 lit. b BGG). Eine Verletzung bundesrechtlicher Verfahrensgarantien, zu deren Rüge die Beschwerdeführer berechtigt wären (BGE 132 I 167 E. 2.1 S. 168), liege nicht vor. Die Gemeinde Rheineck stellt ebenfalls den Antrag, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Sie bringt vor, es bestehe kein Anspruch auf eine Einbürgerung, sondern lediglich ein Anspruch auf Begründung des negativen Einbürgerungsentscheids. Eine Verletzung von Verfahrensrechten (fehlende Begründung) führe bloss zur Aufhebung des mangelhaften Entscheids, nicht aber zur direkten Erteilung des Bürgerrechts durch eine Rechtsmittelinstanz. Einbürgerungsorgan sei nach Art. 104 Abs. 1 KV/SG ausschliesslich die Bürgerschaft, weshalb nicht eine Rechtsmittelinstanz das Gemeindebürgerrecht reformatorisch erteilen könne. Das kantonale Departement des Innern verzichtet auf die Einreichung einer Stellungnahme. Die Beschwerdeführer haben von der Gelegenheit, sich zu den Stellungnahmen des Verwaltungsgerichts und der Gemeinde zu äussern, Gebrauch gemacht. Sie halten darin an ihren Anträgen und Rechtsauffassungen fest.