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.

Das Bundesgericht zieht in Erwägung:
1. Vorliegend ist die Zulässigkeit der durch den Haftrichter bestätigten Ausschaffungshaft zu prüfen, weshalb die Anwendung von Art. 13b ff. des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142.20) und mithin Bundesverwaltungsrecht in Frage steht. Demzufolge ist die Verwaltungsgerichtsbeschwerde zulässig (vgl. Art. 97 ff. OG in Verbindung mit Art. 5 VwVG) und die staatsrechtliche Beschwerde - wie der Beschwerdeführer in seiner Stellungnahme vom 16. September 2004 selber beantragt hat - richtigerweise als solche entgegenzunehmen. Mit Verwaltungsgerichtsbeschwerde kann die Verweigerung der unentgeltlichen Rechtspflege (vgl. Art. 29 Abs. 3 BV) mitangefochten werden.
2. Wurde ein wegen fehlender Reisepapiere oder anderer Schwierigkeiten nicht sofort durchführbarer Wegweisungsentscheid eröffnet, so kann die zuständige kantonale Behörde einen Ausländer zur Sicherstellung des Wegweisungsvollzugs in Ausschaffungshaft nehmen. Voraussetzung hierfür bildet insbesondere, dass ein gesetzlicher Haftgrund vorliegt und die zuständige kantonale richterliche Behörde zustimmt. Weiter darf sich der Vollzug der Wegweisung nicht aus rechtlichen oder tatsächlichen Gründen als undurchführbar erweisen, die Haft muss insgesamt verhältnismässig sein und die für den Vollzug der Weg- oder Ausweisung notwendigen Vorkehrungen müssen umgehend getroffen werden (Art. 13b und Art. 13c ANAG; <ref-ruling> E. 1 S. 58).
3. Nachdem ein (rechtskräftiger) Wegweisungsentscheid der Asylbehörden vorliegt, bleibt zu prüfen, ob der von den kantonalen Behörden herangezogene Haftgrund (Art. 13b Abs. 1 lit. d ANAG, ins Gesetz eingefügt durch das am 19. Dezember 2003 beschlossene "Entlastungsprogramm 2003", in Kraft seit 1. April 2004) erfüllt ist.
3.1 Art. 13b Abs. 1 lit. d ANAG erlaubt neu die Anordnung von Ausschaffungshaft gegen einen Ausländer, wenn das Bundesamt für Flüchtlinge auf dessen Asylgesuch in Anwendung von Art. 32 Abs. 2 lit. a-c oder Art. 33 AsylG nicht eingetreten ist. Gemäss Art. 32 Abs. 2 lit. b AsylG wird auf das Asylgesuch nicht eingetreten, wenn der Asylsuchende die Behörden über seine Identität täuscht und diese Täuschung aufgrund der Ergebnisse der erkennungsdienstlichen Behandlung oder anderer Beweismittel feststeht. Ebenso wird gemäss Art. 32 Abs. 2 lit. c AsylG auf ein Asylgesuch nicht eingetreten, wenn der Asylsuchende seine Mitwirkungspflicht auf eine andere Weise grob verletzt. Gemäss Art. 13f lit. c ANAG (eingefügt am 19. Dezember 2003) muss der Ausländer Ausweispapiere beschaffen oder bei deren Beschaffung durch die Behörden mitwirken. Ebenso verpflichtet Art. 8 Abs. 4 AsylG Asylsuchende dazu, nach Vorliegen eines vollziehbaren Wegweisungsentscheids bei der Beschaffung gültiger Reisepapiere mitzuwirken.
3.2 Nach Wortlaut und Sinn von Art. 13b Abs.1 lit. d ANAG sowie nach der Systematik des Gesetzes stellt das Vorliegen eines gestützt auf Art. 32 Abs. 2 lit. a-c oder Art. 33 AsylG ergangenen Nichteintretensentscheids des Bundesamts für Flüchtlinge schon für sich allein einen (selbständigen) Haftgrund dar, ohne dass es noch (nachträglicher) zusätzlicher Hinweise für eine Untertauchensgefahr oder eine sonstige Vereitelungsabsicht bedürfte. Das folgt auch aus den Erläuterungen in der Botschaft des Bundesrats zum Entlastungsprogramm 2003 für den Bundeshaushalt (BBl 2003 S. 5753 f.) und wurde inzwischen vom Bundesgericht im Grundsatzentscheid vom 15. Juli 2004 (<ref-ruling> E. 3.2.2 f. S. 382 ff.) sowie in einem weiteren Entscheid (Urteil 2A.436/2004 vom 6. August 2004, E. 2.3) bestätigt. Mithin stellt schon die Tatsache, dass das Bundesamt einen auf die genannten Bestimmungen des Asylgesetzes - hier Art. 32 Abs. 2 lit. b AsylG - sich stützenden Nichteintretensentscheid getroffen hat, einen gesetzlichen Haftgrund dar. Wenn die Asylbehörde aufgrund eines bestimmten (missbräuchlichen) Verhaltens des Asylgesuchstellers - in casu: Täuschung der Behörden über seine Identität - einen Nichteintretensentscheid fällt, ist das Vorliegen einer Untertauchensgefahr bzw. der mutmasslichen Absicht, eine zwangsweise Ausschaffung zu vereiteln, von Gesetzes wegen anzunehmen, ohne dass es zur Bejahung des Haftgrunds noch weiterer Elemente bedürfte.
3.3 Dass der Beschwerdeführer im vorliegenden Fall nach dem abschlägigen Asylbescheid nicht untergetaucht ist, sondern sich bei den Behörden wiederholt gemeldet hat, ändert nichts. Im erwähnten Grundsatzurteil vom 15. Juli 2004 lagen die Dinge nicht wesentlich anders: Der Betroffene war nicht untergetaucht, sondern für die Behörden erreichbar, und er wurde - wie der Beschwerdeführer - inhaftiert, als er um finanzielle Nothilfe ersuchte. Wenn das nach dem Nichteintretensentscheid der Asylbehörde zutage gelegte nachträgliche Verhalten zur Beurteilung der unterstellten Vereitelungsabsicht jeweils immer noch als wesentliches Sachverhaltselement mitgewürdigt werden müsste, verlöre der neue Haftgrund gemäss Art. 13b Abs. 1 lit. d ANAG seine Bedeutung oder jedenfalls seinen selbständigen Charakter, und die Bestimmung vermöchte den ihr vom Gesetzgeber zugedachten Zweck nicht zu erfüllen. Eine andere Betrachtungsweise könnte sich allenfalls dann ausnahmsweise rechtfertigen, wenn zwischen dem als Haftgrund heranziehbaren Nichteintretensentscheid der Asylbehörde und der Anordnung der Ausschaffungshaft lange Zeit verstrichen ist und sich eine Berücksichtigung der nachträglichen Entwicklung der Dinge zur Beurteilung der Untertauchensgefahr sachlich zwingend aufdrängt. Vorbehalten bleibt in jedem Fall die allgemeine Schranke der Verhältnismässigkeit: Auf die Anordnung oder Aufrechterhaltung der Ausschaffungshaft ist zu verzichten, wenn diese Massnahme wegen bestimmter äusserer Umstände nicht bzw. nicht mehr als sinnvoll und verhältnismässig erscheint, z.B. weil binnen kurzem mit der Erteilung einer Aufenthaltsbewilligung zu rechnen ist (vgl. <ref-ruling> E. 4; <ref-ruling> E. 4 S. 383; vgl. auch <ref-ruling> E. 4.2.3 S. 62 f.).
3.4 Vorliegend erfolgte die Anordnung der Ausschaffungshaft als Reaktion auf die Nichtbefolgung der mit dem asylrechtlichen Nichteintretensentscheid verbundenen Wegweisung, ohne dass bis zur Haftanordnung ein übermässig langer Zeitraum verstrichen wäre. Damit genügte die Erfüllung der Voraussetzungen von Art. 13b Abs. 1 lit. d ANAG schon für sich allein als Haftgrund. Dem Hinweis des Beschwerdeführers auf sein nachträgliches Verhalten wäre im Übrigen entgegenzuhalten, dass aus seinem bisherigen Nichtuntertauchen bzw. dem wiederholten Vorsprechen bei den kantonalen Einwohnerdiensten auch rein sachlich nicht (oder nicht ohne weiteres) auf das Fehlen der unterstellten Vereitelungsabsicht geschlossen werden könnte. Dieses Verhalten des Beschwerdeführers lässt sich nämlich auch damit erklären, dass er entweder aufgrund der ungeklärten Identität bzw. der fehlenden Papiere gar nicht mit der Möglichkeit rechnete, zwecks zwangsweiser Ausschaffung bereits in Haft genommen zu werden (vgl. <ref-ruling> E. 3.3.3.2 S. 387), oder dass er, weil an Unterstützungsleistungen interessiert, trotz an sich weiterbestehender Untertauchensabsicht bei der Behörde vorsprach und das damit verbundene Risiko einer allfälligen Inhaftierung bewusst hinnahm. Wer seine Mitwirkungspflichten im Asylverfahren gröblich verletzt und deswegen einen Nichteintretensentscheid erwirkt, muss gemäss der neuen gesetzlichen - mit der EMRK grundsätzlich im Einklang stehenden (vgl. <ref-ruling> E. 3.1 S. 380, E. 3.2.3 i.f.S. 384 und E. 3.3 S. 385 ff.) - Regelung jedenfalls in Kauf nehmen, dass er zur Sicherung des zwangsweisen Vollzugs der Wegweisung in Ausschaffungshaft genommen wird. Dazu kommt vorliegend, dass der Beschwerdeführer die ihm nach Art. 13f ANAG obliegende bzw. auferlegte Mitwirkung bei der Papierbeschaffung auch nachträglich verweigert hat, was einen zusätzlichen Haftgrund darstellen könnte (vgl. Art. 13b Abs. 1 lit. c ANAG in der Fassung 19. Dezember 2003). Die Einwendungen des Beschwerdeführers sind insoweit nicht stichhaltig.
4. Vorbehalten bleiben die übrigen gesetzlichen Voraussetzungen für die Ausschaffungshaft, wobei hier einzig noch die Einhaltung des Beschleunigungsgebots in Frage steht.
4.1 Der Beschwerdeführer wurde, weil er nach dem Entscheid der Asylrekurskommission seiner Ausreisepflicht nicht nachgekommen war und auch nichts zur Beschaffung der erforderlichen Papiere unternommen hatte, am 24. August 2004 in Ausschaffungshaft versetzt und diese Anordnung tagsdarauf vom Haftrichter bestätigt. Gemäss Art. 13b Abs. 3 ANAG sind die für den Vollzug der Wegweisung notwendigen Vorkehren umgehend zu treffen. Befindet sich der weggewiesene Ausländer in Untersuchungshaft oder im Strafvollzug, so sind die Fremdenpolizeibehörden bei klarer fremdenpolizeilicher Ausgangslage nach der Rechtsprechung des Bundesgerichtes gehalten, die notwendigen Schritte zur Papierbeschaffung nach Möglichkeit schon vor der Entlassung einzuleiten, damit der Betroffene nicht mehr unnötig oder nicht unnötig lange in Ausschaffungshaft genommen werden muss (vgl. <ref-ruling> E. 3a, mit Hinweisen).
4.2 Auf diese Rechtsprechung kann sich der Beschwerdeführer vorliegend nicht berufen: Die gegen ihn verfügte Wegweisung wurde mit dem Entscheid der Asylrekurskommission rechtskräftig, und dem Beschwerdeführer wurde zunächst Gelegenheit gegeben, selber die erforderlichen Schritte zur Papierbeschaffung für die Ausreise zu unternehmen. Erst als sich zeigte, dass der Beschwerdeführer dazu nicht gewillt war, wurde die Notwendigkeit einer zwangsweisen Ausschaffung sichtbar. Im Zeitpunkt der Haftanordnung bzw. -bestätigung durch den Richter konnte demzufolge von einer unzulässigen Verzögerung der behördlichen Vorkehren zur Papierbeschaffung keine Rede sein. Die vom Beschwerdeführer angerufene Rechtsprechung, wonach Untätigkeit der Behörden während mehr als zwei Monaten als Verletzung des Beschleunigungsgebots zu werten ist (vgl. <ref-ruling> E. 3a S. 51), kommt hier nicht zum Zuge. Wieweit das Beschleunigungsgebot seit Anordnung der Haft eingehalten worden ist, kann nicht Gegenstand des vorliegenden Verfahrens bilden. Im Übrigen haben die baselstädtischen Behörden sofort nach Anordnung der Ausschaffungshaft um Vollzugsunterstützung durch den Bund ersucht.
5. Nicht durchzudringen vermag auch der Eventualantrag des Beschwerdeführers: Da es im angefochtenen Entscheid um die erstmalige Anordnung der Ausschaffungshaft ging, liegt in der Verweigerung der Beigabe eines unentgeltlichen Rechtsbeistandes keine Verfassungsverletzung. Es stellten sich aufgrund des geänderten Gesetzes zwar neue Rechtsfragen, welche aber durch die beiden genannten und den Beteiligten bekannten Bundesgerichtsurteile im Wesentlichen (bezüglich der Selbständigkeit der neuen Haftgründe) bereits beantwortet waren. Der kantonale Haftrichter durfte daher eine amtliche Verbeiständung ohne Verletzung von Art. 29 Abs. 3 BV verweigern (vgl. <ref-ruling> E. 3c S. 278).
6. Die Verwaltungsgerichtsbeschwerde erweist sich nach dem Gesagten als unbegründet und ist abzuweisen. Bei diesem Verfahrensausgang wird der Beschwerdeführer grundsätzlich kostenpflichtig (vgl. Art. 156 OG). Aufgrund der dem Beschwerdeführer bekannten Rechtsprechung fehlte es dem beim Bundesgericht eingelegten Rechtsmittel an der erforderlichen Erfolgsaussicht (vgl. Art. 152 Abs. 1 OG), sowohl was das Vorliegen eines Haftgrunds wie auch was die Frage des Beschleunigungsgebots anbelangt. Das Gesuch um unentgeltliche Rechtspflege und amtliche Verbeiständung ist deshalb abzuweisen. In Fällen der vorliegenden Art rechtfertigt es sich allerdings, von der Erhebung einer Gerichtsgebühr abzusehen (Art. 154 und Art. 153a Abs. 1 OG). Eine Parteientschädigung ist nicht auszurichten (Art. 159 OG).

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird als Verwaltungsgerichtsbeschwerde entgegengenommen.
2. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
3. Das Gesuch um unentgeltliche Rechtspflege und amtliche Verbeiständung wird abgewiesen.
4. Es werden keine Kosten erhoben.
5. Dieses Urteil wird dem Beschwerdeführer, den Einwohnerdiensten des Kantons Basel-Stadt, Abteilung Internationale Kundschaft als kantonale Fremdenpolizei, und dem Verwaltungsgericht des Kantons Basel-Stadt, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, sowie dem Bundesamt für Flüchtlinge schriftlich mitgeteilt.
Lausanne, 30. September 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: