Sachverhalt: A. Der nach eigenen Angaben aus Weissrussland stammende, papierlose X._ ist am 8. Juni 2004 illegal in die Schweiz eingereist, wo er gleichentags um Asyl ersuchte. Das Bundesamt für Flüchtlinge trat am 22. Juni 2004 auf sein Gesuch nicht ein, wies ihn weg und hielt ihn an, spätestens am Tag nach Eintritt der Rechtskraft seines Entscheids die Schweiz zu verlassen. Das Bundesamt begründete dies damit, dass X._ die Behörden über seine Herkunft getäuscht habe (vgl. Art. 32 Abs. 2 lit. b des Asylgesetzes vom 26. Juni 1998 [AsylG; SR 142.31]); weil er offensichtlich nicht aus Weissrussland stamme und sich seine Ausführungen nur auf dieses Land bezögen, lägen zudem keinerlei Hinweise auf eine Gefährdung vor. Am 5. Juli 2004 schützte die Schweizerische Asylrekurskommission den Nichteintretensentscheid auf Beschwerde hin, wobei sie eine Ausweisung nach Weissrussland ausschloss. B. X._ sprach mehrmals (12. Juli, 3. und 23. August 2004) bei den Einwohnerdiensten des Kantons Basel-Stadt vor und ersuchte um finanzielle Nothilfe. Zudem wurde er am 14. Juli 2004 von der Polizei vorgeführt und bei dieser Gelegenheit ausdrücklich auf seine Mitwirkungspflicht bei der Papierbeschaffung sowie auf die Möglichkeit, ihn in Ausschaffungshaft zu nehmen, hingewiesen. Anlässlich der Vorsprache vom 23. August 2004 wurde X._ verhaftet und mit Strafbefehl des Strafgerichts Basel-Stadt vom 24. August 2004 wegen rechtswidrigen Aufenthalts in der Schweiz zu einer Busse von 400 Franken verurteilt. Anschliessend wurde er von den Einwohnerdiensten in Ausschaffungshaft genommen, welche das Verwaltungsgericht des Kantons Basel-Stadt, Einzelrichter für Zwangsmassnahmen im Ausländerrecht (Haftrichter), bis zum 23. November 2004 bestätigte (Urteil vom 25. August 2004). Gleichzeitig wies der Haftrichter das Gesuch um amtliche Verbeiständung ab. C. Am 8. September 2004 hat X._ beim Bundesgericht staatsrechtliche Beschwerde eingereicht mit dem Antrag, den Entscheid des Haftrichters aufzuheben und die Einwohnerdienste des Kantons Basel-Stadt anzuweisen, ihn aus der Haft zu entlassen. Eventuell sei der angefochtene Entscheid insoweit aufzuheben, als ihm die amtliche Verbeiständung verweigert worden sei. Weiter hat der Beschwerdeführer für das bundesgerichtliche Verfahren um Gewährung der unentgeltlichen Rechtspflege und um amtliche Verbeiständung ersucht. D. Der Haftrichter beantragt, auf die Beschwerde nicht einzutreten, eventuell sie abzuweisen. Die Einwohnerdienste schliessen auf Abweisung der Beschwerde. X._ hat mit Stellungnahme vom 16. September 2004 an seinen Anträgen und Ausführungen festgehalten, aber um Behandlung seiner Eingabe als Verwaltungsgerichtsbeschwerde ersucht.