Sachverhalt: Sachverhalt: A. Der Vertrag zwischen der Schweizerischen Eidgenossenschaft und dem Grossherzogtum Baden betreffend die Weiterführung der badischen Eisenbahnen über schweizerisches Gebiet vom 27. Juli 1852 räumt der deutschen Seite das Recht ein, über schweizerisches Gebiet eine Verbindungsstrasse (Zollfreie Strasse) zwischen den Städten Lörrach und Weil am Rhein zu bauen. Ein vom Regierungspräsidium Freiburg im Breisgau ausgearbeitetes "Auflageprojekt vom November 1974" wurde öffentlich aufgelegt und in der Folge aufgrund von Einsprachen überarbeitet. Der Regierungsrat des Kantons Basel-Stadt genehmigte am 16. Dezember 1975 das überarbeitete Projekt mit verschiedenen Auflagen und Bedingungen. Am 7. Mai 1976 trafen das Land Baden-Württemberg und der Kanton Basel-Stadt eine Vereinbarung über die technischen Einzelheiten im Zusammenhang mit dem Bau, Betrieb und Unterhalt der Verbindungsstrasse. In der Folge schlossen die Schweizerische Eidgenossenschaft und die Bundesrepublik Deutschland am 25. April 1977 einen Staatsvertrag über die Verbindungsstrasse ab (SR 0.725.122). Gemäss diesem bestimmen sich Linienführung und Bau der Strasse nach dem vom Regierungsrat des Kantons Basel-Stadt genehmigten Auflageprojekt, wobei auf einen dem Vertrag beigefügten "Rahmenplan" verwiesen wird (Art. 2). Der Staatsvertrag ist am 14. Dezember 1979 von der Bundesversammlung ratifiziert worden und am 1. August 1980 in Kraft getreten. A. Der Vertrag zwischen der Schweizerischen Eidgenossenschaft und dem Grossherzogtum Baden betreffend die Weiterführung der badischen Eisenbahnen über schweizerisches Gebiet vom 27. Juli 1852 räumt der deutschen Seite das Recht ein, über schweizerisches Gebiet eine Verbindungsstrasse (Zollfreie Strasse) zwischen den Städten Lörrach und Weil am Rhein zu bauen. Ein vom Regierungspräsidium Freiburg im Breisgau ausgearbeitetes "Auflageprojekt vom November 1974" wurde öffentlich aufgelegt und in der Folge aufgrund von Einsprachen überarbeitet. Der Regierungsrat des Kantons Basel-Stadt genehmigte am 16. Dezember 1975 das überarbeitete Projekt mit verschiedenen Auflagen und Bedingungen. Am 7. Mai 1976 trafen das Land Baden-Württemberg und der Kanton Basel-Stadt eine Vereinbarung über die technischen Einzelheiten im Zusammenhang mit dem Bau, Betrieb und Unterhalt der Verbindungsstrasse. In der Folge schlossen die Schweizerische Eidgenossenschaft und die Bundesrepublik Deutschland am 25. April 1977 einen Staatsvertrag über die Verbindungsstrasse ab (SR 0.725.122). Gemäss diesem bestimmen sich Linienführung und Bau der Strasse nach dem vom Regierungsrat des Kantons Basel-Stadt genehmigten Auflageprojekt, wobei auf einen dem Vertrag beigefügten "Rahmenplan" verwiesen wird (Art. 2). Der Staatsvertrag ist am 14. Dezember 1979 von der Bundesversammlung ratifiziert worden und am 1. August 1980 in Kraft getreten. B. Mit Beschluss vom 4. April 1995 erteilte der Regierungsrat des Kantons Basel-Stadt dem Regierungspräsidium Freiburg im Breisgau eine auf fünf Jahre befristete Bewilligung zur Rodung von 2090 m2 Wald in Riehen auf den Parzellen Nrn. A013600 und A013700 zum Bau der Zollfreien Strasse. Das Bundesgericht wies die dagegen eingereichten Beschwerden ab und hielt in BGE 122 II 234 E. 4b-d S. 237 f. fest, der Staatsvertrag regle abschliessend, unter welchen Voraussetzungen der Vertragszweck erreicht werden solle. Die Verwirklichung der Verbindungsstrasse solle nicht vom Ergebnis nachfolgender landesinterner Bewilligungsverfahren abhängen. Die bewilligte Rodung verletze weder Art. 5 des Bundesgesetzes über den Wald vom 4. Oktober 1991 (WaG; SR 921.0) noch Koordinationsgrundsätze (a.a.O., E. 4e S. 240). B. Mit Beschluss vom 4. April 1995 erteilte der Regierungsrat des Kantons Basel-Stadt dem Regierungspräsidium Freiburg im Breisgau eine auf fünf Jahre befristete Bewilligung zur Rodung von 2090 m2 Wald in Riehen auf den Parzellen Nrn. A013600 und A013700 zum Bau der Zollfreien Strasse. Das Bundesgericht wies die dagegen eingereichten Beschwerden ab und hielt in BGE 122 II 234 E. 4b-d S. 237 f. fest, der Staatsvertrag regle abschliessend, unter welchen Voraussetzungen der Vertragszweck erreicht werden solle. Die Verwirklichung der Verbindungsstrasse solle nicht vom Ergebnis nachfolgender landesinterner Bewilligungsverfahren abhängen. Die bewilligte Rodung verletze weder Art. 5 des Bundesgesetzes über den Wald vom 4. Oktober 1991 (WaG; SR 921.0) noch Koordinationsgrundsätze (a.a.O., E. 4e S. 240). C. Wegen Verzögerungen im Baubewilligungsverfahren drohte die auf den 26. Juni 2001 befristete Rodungsbewilligung unbenutzt abzulaufen. Auf Gesuch des Regierungspräsidiums Freiburg hin, verlängerte der Regierungsrat des Kantons Basel-Stadt die Rodungsbewilligung am 29. Mai 2001 bis zum 30. Juni 2006. Dieser Beschluss wurde zahlreichen Institutionen und Verbänden eröffnet, nicht jedoch den privaten Rekurrenten des ersten Rodungsbewilligungsverfahrens. Am 24. Juni 2004 erhoben X._ sowie Y._ Rekurs beim Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht), nachdem ihnen auf Anfrage der Entwurf der Rodungsbewilligungsverlängerung vom 29. Mai 2001 zugestellt worden war. In ihrer Rekursbegründung vom 27. August 2004 beantragten sie, es sei festzuhalten, dass die Rodungsbewilligungsverlängerung nichtig sei. Die Rodungsbewilligungsverlängerung sei aufzuheben oder eventualiter an die Vorinstanz zur erneuten Prüfung zurückzuweisen. Gleichzeitig stellten sie u.a. den "dringenden" Antrag um Zuerkennung der aufschiebenden Wirkung. Am 24. Juni 2004 erhoben X._ sowie Y._ Rekurs beim Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht), nachdem ihnen auf Anfrage der Entwurf der Rodungsbewilligungsverlängerung vom 29. Mai 2001 zugestellt worden war. In ihrer Rekursbegründung vom 27. August 2004 beantragten sie, es sei festzuhalten, dass die Rodungsbewilligungsverlängerung nichtig sei. Die Rodungsbewilligungsverlängerung sei aufzuheben oder eventualiter an die Vorinstanz zur erneuten Prüfung zurückzuweisen. Gleichzeitig stellten sie u.a. den "dringenden" Antrag um Zuerkennung der aufschiebenden Wirkung. D. Am 3. September 2004 wies die Präsidentin des Appellationsgerichts (als Verwaltungsgericht) das Gesuch um Erteilung der aufschiebenden Wirkung ab, da die Aussichten des Rekurses sowohl aus formellen wie auch aus materiellen Gründen mit grossen Risiken behaftet seien. In Ziff. 2 der Verfügung wurde festgehalten, dass - sollte das Verwaltungsgericht den Rekurs gutheissen - der Vorzustand wieder hergestellt werden müsse. Mit Eingabe vom 7. September 2004 gelangen X._ sowie Y._ an das Bundesgericht. In ihren Rechtsbegehren verlangen sie die Aufhebung der angefochtenen Verfügung vom 3. September 2004 sowie die Gewährung der aufschiebenden Wirkung. Als superprovisorische, eventuell provisorische Massnahme beantragen sie, den Regierungsrat des Kantons Basel-Stadt respektive die Bauherrschaft anzuweisen, zumindest während dem bundesgerichtlichen Verfahren den bestehenden Zustand zu erhalten und die Rodung zu unterlassen. Mit Verfügung vom 8. September 2004 untersagte das Bundesgericht sämtliche Vollziehungsvorkehrungen. Das Appellationsgericht und der Regierungsrat des Kantons Basel-Stadt schliessen auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Der Regierungsrat beantragt überdies, die vorsorglich getroffene Massnahme, wonach Vollziehungsvorkehrungen zu unterbleiben haben, sei umgehend aufzuheben. Mit Beschwerdeergänzung vom 15. September 2004 bezeichnen die Beschwerdeführer ihre Eingabe als Verwaltungsgerichtsbeschwerde und berufen sich zusätzlich auf Art. 47 WaG.