Sachverhalt: A. Das Bundesamt für Flüchtlinge trat am 8. April 2004 auf ein Asylgesuch von X._ (geb. 1987) nicht ein, da er vermutlich nicht - wie von ihm behauptet - aus Kamerun, sondern vielmehr aus Nigeria stammen dürfte; es forderte ihn auf, das Land umgehend zu verlassen. Dieser Entscheid wurde rechtskräftig. X._ befolgte die ihm auferlegte Wegweisung indessen nicht. Seit dem 4. Juni 2004 musste ihn das Amt für Gemeinden und soziale Sicherheit des Kantons Solothurn in der Folge während 147 Tagen mit Nothilfeleistungen von insgesamt Fr. 3'087.-- unterstützen. Mit Verfügung vom 29. Oktober 2004 entschied das Departement des Innern des Kantons Solothurn, dass X._ keine ordentliche Nothilfe, sondern lediglich noch ein "Zehrgeld" für fünf Tage von insgesamt Fr. 105.-- ausgerichtet werde. Sollte er in dieser Zeit nicht ausreisen, erhalte er keine weiteren Hilfeleistungen mehr; nur falls er rechtsgenüglich zu beweisen vermöge, dass er sich um eine Rückkehr in seine Heimat ernsthaft bemüht habe, werde ein Antrag auf Ausrichtung zusätzlicher Nothilfe gegebenenfalls neu geprüft. Am 10. November 2004 wies das Verwaltungsgericht des Kantons Solothurn die dagegen gerichtete Beschwerde von X._ ab, soweit es darauf eintrat. Dabei verneinte es insbesondere eine Verletzung von Art. 12 BV (Recht auf Hilfe in Notlagen), da der Beschwerdeführer, falls er sein Verhalten ändere und bei der Organisation seiner Ausreise kooperiere, befristet Zugang zu weiteren Nothilfeleistungen erhalten könne. B. Gegen das Urteil des Verwaltungsgerichts erhob X._ am 16. Dezember 2004 staatsrechtliche Beschwerde beim Bundesgericht mit den folgenden Anträgen: "1. Das angefochtene Urteil der Vorinstanz sei aufzuheben und die Sache sei zur neuen Entscheidung an die Vorinstanz zurückzuweisen; 2. es sei festzustellen, dass § 4 Abs. 4 der Vollzugsverordnung zum Gesetz über die öffentliche Sozialhilfe des Kantons Solothurn Art. 8 BV und Art. 7 KV verletzt; 3. es sei festzustellen, dass der Beschluss des Regierungsrates des Kantons Solothurn vom 18. Mai 2004 (Nr. 2004/1051) betreffend Richtlinien über die Ausgestaltung der Nothilfe an Personen ausländischer Staatsangehörigkeit mit Nichteintretensentscheid nach Art. 32 ff. Asylgesetz insoweit Art. 12 BV und Art. 6 KV verletzt, als er die Nothilfe von vornherein auf wenige Tage, maximal aber 5 Tage befristet, und keinen effektiven Zugang zu einem Obdach mit Übernachtungsmöglichkeit gewährt; ..." Das Departement des Innern des Kantons Solothurn schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Solothurn beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. C. Mit superprovisorischer Verfügung vom 23. Dezember 2004 bzw. mit vorsorglicher Verfügung vom 25. Januar 2005 ordnete der Präsident der II. öffentlichrechtlichen Abteilung des Bundesgerichts an, X._ seien während der Dauer des bundesgerichtlichen Verfahrens die vom Kanton Solothurn im bisherigen Umfang erbrachten Nothilfeleistungen weiterhin auszurichten.