Sachverhalt:
A. X._ reiste am 20. Juni 1998 ohne Pass und Visum in die Schweiz ein. Gleichentags stellte er in Genf ein Asylgesuch. Mit Entscheid vom 21. Januar 2000 trat das Bundesamt für Flüchtlinge (BFF) auf das Asylgesuch nicht ein und forderte X._ auf, sofort auszureisen. Mit Entscheid vom 23. Mai 2000 bestätigte die Schweizerische Asylrekurskommission den Entscheid des BFF. Da X._ der Wegweisungsanordnung (trotz angedrohter strafrechtlicher Konsequenzen) keine Folge leistete und seine Mitwirkung bei der Identitätsabklärung verweigerte, wurde er am 3. Januar 2003 vom Amt für Migration des Kantons Luzern erstmals wegen illegaler Einreise und illegalem Aufenthalt verzeigt. In der Folge wurde X._ mehrmals einschlägig bestraft. Am 23. Juni 2004 verurteilte ihn das Amtsgericht Luzern-Stadt letztmals rechtskräftig (wegen Widerhandlung gegen Art. 23 Abs. 1 al. 4 ANAG, begangen zwischen 4. Januar und 27. Oktober 2003) zu einer bedingten Gefängnisstrafe von einem Monat. Gleichzeitig widerrief es den in einer früheren Strafverfügung gewährten bedingten Strafvollzug für eine dreimonatige Gefängnisstrafe.
B. Am 17. August 2004 wurde X._ beim Luzerner Bahnhof polizeilich kontrolliert und verhaftet. Mit Verfügung des Amtsstatthalteramtes Luzern-Stadt (Amtsstatthalter Y._) vom 18. August 2004 wurde X._ wegen erneuter Widerhandlung gegen das ANAG in Untersuchungshaft versetzt. Auf Rekurs des Inhaftierten hin bestätigte das Obergericht, II. Kammer, des Kantons Luzern mit Entscheid vom 31. August 2004 die Haftanordnung.
C. Mit Strafverfügung vom 13. September 2004 fällte das Amtsstatthalteramt Luzern (Amtsstatthalter Y._) eine Gefängnisstrafe von drei Monaten (unbedingt) gegen X._ wegen Widerhandlung gegen Art. 23 Abs. 1 al. 4 ANAG aus. Der im Urteil des Amtsgerichtes Luzern-Stadt vom 23. Juni 2004 gewährte bedingte Strafvollzug wurde widerrufen. Da der Angeschuldigte die Strafverfügung vom 13. September 2004 nicht annahm, überwies das Amtsstatthalteramt Luzern-Stadt (Amtsstatthalter Y._) die Strafsache am 15./20. September 2004 an das Amtsgericht Luzern-Stadt.
D. Gegen den Haftrekursentscheid des Obergerichtes vom 31. August 2004 gelangte X._ mit staatsrechtlicher Beschwerde vom 28. September 2004 an das Bundesgericht. Er rügt unter anderem eine Verletzung der persönlichen Freiheit bzw. seines Anspruches auf unverzügliche Vorführung vor einen unabhängigen Haftrichter (<ref-law>), und er beantragt neben der Aufhebung des angefochtenen Entscheides seine Haftentlassung.
E. Das Obergericht und die Staatsanwaltschaft des Kantons Luzern beantragen mit Stellungnahmen vom 7. bzw. 11. Oktober 2004 je die Abweisung der Beschwerde, soweit darauf einzutreten ist. Vom Amtsstatthalteramt Luzern-Stadt ist keine Vernehmlassung eingegangen. Mit Beschluss vom 19. Oktober 2004 bewilligte das Bundesgericht das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege. Der Beschwerdeführer replizierte am 21. Oktober 2004.

Das Bundesgericht zieht in Erwägung:
1. Der Beschwerdeführer beantragt neben der Aufhebung des angefochtenen Entscheides seine Haftentlassung. Dieses Begehren ist in Abweichung vom Grundsatz der kassatorischen Natur der staatsrechtlichen Beschwerde zulässig, da im Falle einer nicht gerechtfertigten strafprozessualen Haft die von der Verfassung geforderte Lage nicht schon mit der Aufhebung des angefochtenen Entscheids sondern erst durch eine positive Anordnung hergestellt werden kann (<ref-ruling> E. 1.2.1 S. 131 f.; <ref-ruling> E. 4a S. 332; <ref-ruling> E. 1a S. 296 f., je mit Hinweisen).
Auch die übrigen Sachurteilsvoraussetzungen von Art. 84 ff. OG sind grundsätzlich erfüllt.
2. Der Beschwerdeführer macht geltend, bei der Anordnung der Untersuchungshaft sei sein grundrechtlicher Anspruch auf unverzügliche Vorführung vor eine unabhängige Richterin oder einen Richter verletzt worden. Der gleiche Amtsstatthalter, der die Haft gegen ihn angeordnet habe, habe in der nämlichen Strafsache gegen den Beschwerdeführer ermittelt, am 13. September 2004 eine Strafverfügung erlassen und (nach unterbliebener Annahme der Strafverfügung durch den Angeschuldigten) die Überweisung an das Strafgericht vorgenommen. Der Amtsstatthalter erfülle daher die Anforderungen an einen unabhängigen Haftrichter im Sinne von <ref-law> und Art. 5 Ziff. 3 EMRK nicht.
2.1 Im angefochtenen Entscheid wird erwogen, der luzernische Amtsstatthalter erfülle "als Haftrichter die Anforderungen an Art. 5 Ziff. 3 EMRK". Er vertrete nicht die Anklage vor Gericht und sei "deshalb auch nicht Partei". Ausserdem werde er "vom Volk gewählt". Die Aufsicht der Staatsanwaltschaft erstrecke sich "nicht auf die Haftkompetenzen des Amtsstatthalters". Dementsprechend sehe das Luzerner Strafprozessrecht "die Kompetenz des Amtsstatthalters zum Erlass des Haftbefehls und der Haftverfügung ausdrücklich vor".
2.2 Die Aufgaben und Zuständigkeiten des Amtsstatthalters und der Staatsanwaltschaft sind im luzernischen Strafprozessrecht wie folgt geregelt: Der Amtsstatthalter leitet die Strafuntersuchung und schliesst diese ab (§§ 60 ff., namentlich §§ 60 Abs. 1, 63 Abs. 1 und 124 StPO/LU; vgl. auch §§ 10, 34 Abs. 1, 49 Abs. 3, 58, 59 Abs. 1, 81 Abs. 2, 86 Abs. 1, 89bis Abs. 3, 89quater und 103 ff. StPO/LU). Die Staatsanwaltschaft "übt die unmittelbare Aufsicht über die Amtsstatthalter aus"; sie "überwacht die Strafuntersuchungen, insbesondere ihre richtige und beförderliche Erledigung" (<ref-law>/LU). Der Staatsanwalt "kann Bericht über den Stand der Untersuchungen einverlangen, Weisungen erteilen und den Untersuchungshandlungen beiwohnen" (<ref-law>/LU); er "prüft die Geschäftsführung des Amtsstatthalters, trifft die nötigen Anordnungen und erstattet der Kriminal- und Anklagekommission Bericht" (<ref-law>/LU). Der Staatsanwalt prüft alle eingestellten und von der Hand gewiesenen Untersuchungen sowie die mit Strafverfügung erledigten Untersuchungen, die sein Visum benötigen (<ref-law>/LU).
Bestehen nach Durchführung der Strafuntersuchung hinreichende Anhaltspunkte für eine strafbare Handlung, überweist der Amtsstatthalter den Fall dem zuständigen Gericht (<ref-law>/LU). Das Überweisungserkanntnis enthält unter anderem den inkriminierten Sachverhalt mit Hinweis auf die Belegstellen und die anwendbaren Gesetzesbestimmungen (<ref-law>/LU). Ist das Amtsgericht oder das Obergericht zuständig, stellt der Amtsstatthalter einen schriftlichen Antrag über Schuld, Strafe und Massnahmen (<ref-law>/LU). Der Amtsstatthalter schliesst die Untersuchung mit einer Strafverfügung ab, wenn diese auf höchstens drei Monate Freiheitsentzug lautet (<ref-law>/LU). Auch die Strafverfügung enthält den inkriminierten Sachverhalt sowie den Schuldbefund und eine Begründung, von der in einfachen Fällen abgesehen werden kann (<ref-law>/LU).
Lautet die Strafverfügung auf eine Freiheitsstrafe allein oder in Verbindung mit einer anderen Strafe oder Massnahme, kann der Angeschuldigte innert 20 Tagen die Strafverfügung durch schriftliche Erklärung annehmen (<ref-law>/LU). Nimmt der Angeschuldigte die Strafverfügung nicht an, wird die Untersuchung ergänzt oder die Sache dem zuständigen Gericht überwiesen (<ref-law>/LU).
Eine "Abschrift der Anklage" wird dem Angeschuldigten und seinem Verteidiger vor der Gerichtsverhandlung zugestellt (<ref-law>/ LU). Zu Beginn der Gerichtsverhandlung eröffnet der Präsident nochmals "die Anträge des Amtsstatthalters oder des Staatsanwalts, wenn eine Partei dies verlangt" (<ref-law>/LU "Eröffnung der Anklage"). Bei kriminalgerichtlicher Zuständigkeit erhebt der Staatsanwalt die Anklage (<ref-law>/LU). Ist das Amtsgericht oder das Obergericht zuständig, stellt der Amtsstatthalter den schriftlichen Antrag über Schuld, Strafe und Massnahmen (<ref-law>/LU). Erfolgt eine Anklage durch den Staatsanwalt darf diese "nicht durch den gleichen Staatsanwalt erhoben werden, der zuvor bereits einen Haftbefehl gegen den Angeschuldigten erlassen hat" (<ref-law>/LU).
Das luzernische Strafprozessrecht sieht schliesslich vor, dass der Amtsstatthalter auch über die Anordnung von Untersuchungshaft entscheidet (§ 52 Abs. 2 sowie § 83bis Abs. 1 StPO/LU). Haftbefehle werden vom Amtsstatthalter, vom Staatsanwalt oder von den zuständigen Strafgerichten bzw. ihren Präsidenten erlassen (<ref-law>/LU). Haftverfügungen des Amtsstatthalters, des Staatsanwaltes und der unteren Gerichte können mit Rekurs beim kantonalen Obergericht angefochten werden (§ 83bis Abs. 2 und § 83quater Abs. 3 StPO/LU). Im Gerichts- und Rechtsmittelverfahren ist die Staatsanwaltschaft Partei des Strafverfahrens (<ref-law>/LU).
2.3 Art. 5 Ziff. 3 EMRK verlangt, dass jede in strafprozessualer Haft gehaltene Person unverzüglich einem Richter oder einem anderen, gesetzlich zur Ausübung richterlicher Funktionen ermächtigten Beamten vorgeführt werden muss ("doit être aussitôt traduite devant un juge ou un autre magistrat habilité par la loi à exercer des fonctions judiciaires"/"shall brought promptly before a judge or another officer authorised by law to exercise judicial power"). Nach übereinstimmender Lehre und Rechtsprechung muss es sich beim haftanordnenden Magistraten im Sinne von Art. 5 Ziff. 3 EMRK um eine unparteiische Instanz handeln, die von der Exekutive und den Parteien unabhängig und bei der Ausübung ihres Amtes nicht weisungsgebunden ist. Sie muss in einem justiziellen Verfahren entscheiden, den Inhaftierten persönlich anhören, insbesondere die Angemessenheit der Haft prüfen und nötigenfalls die Haftentlassung anordnen können (<ref-ruling> E. 7a S. 231; <ref-ruling> E. 3b S. 98; EGMR vom 5. April 2001 i.S. H. B. c. CH, JAAC 2001 Nr. 120 S. 1292, Ziff. 55, je mit Hinweisen; vgl. auch Jochen A. Frowein/Wolfgang Peukert, EMRK-Kommentar, 2. Aufl., Kehl u.a. 1996, Art. 5 N. 117; Arthur Haefliger/Frank Schürmann, Die Europäische Menschenrechtskonvention und die Schweiz, 2. Aufl., Bern 1999, S. 112). Nach der bundesgerichtlichen Praxis ist Art. 5 Ziff. 3 EMRK namentlich verletzt, wenn die haftanordnende Amtsperson in gleicher Sache auch noch für die Anklageerhebung zuständig ist (<ref-ruling> E. 3c S. 279; <ref-ruling> E. 7c S. 234; <ref-ruling> E. 3c S. 98, E. 3d-e S. 99 f.; <ref-ruling> E. 4b-c S. 201 f., je mit Hinweisen).
Im Fall Schiesser hatte der Europäische Gerichtshof für Menschenrechte (EGMR) erwogen, dass Zürcher Bezirksanwälte die Voraussetzungen von Art. 5 Ziff. 3 EMRK grundsätzlich erfüllen könnten, sofern eine personelle Trennung zwischen haftrichterlicher Funktion einerseits und Untersuchungs- bzw. Anklagefunktion anderseits gewährleistet wird (EGMR vom 4. Dezember 1980 i.S. Schiesser c. CH, Série A, vol. 34, Ziff. 31 = EuGRZ 1980, S. 201). Im Fall Jutta Huber hat der EGMR eine Verletzung der EMRK durch die Schweiz festgestellt, da der gleiche Zürcher Bezirksanwalt sowohl für die Haftanordnung als auch für die Anklageerhebung zuständig war (EGMR vom 23. Oktober 1990 i.S. Huber c. CH, Série A, vol. 188, Ziff. 42 f. = EuGRZ 1990, S. 502). Entscheidend für die Beurteilung, ob der haftanordnende Magistrat ausreichend unabhängig erscheint, ist nach der Praxis des EGMR der objektive Anschein im Zeitpunkt der Haftanordnung. Der Eindruck der Unvoreingenommenheit fällt grundsätzlich schon dahin, wenn aufgrund der Prozessordnung die Möglichkeit besteht, dass der haftanordnende Magistrat in der Folge Anklagefunktionen ausüben könnte (EGMR vom 26. November 1992 i.S. Brincat c. I, Série A, vol. 249-A = EuGRZ 1993, S. 389; EGMR vom 5. April 2001 i.S. H. B. c. CH, JAAC 2001 Nr. 120 S. 1292, Ziff. 55, 57, 62 f.; EGMR i.S. Huber c. CH, a.a.O., Ziff. 40, je mit Hinweisen; vgl. auch BGE <ref-ruling> E. 3a S. 97; <ref-ruling> E. 4b S. 201).
Diese Praxis wurde vom EGMR (bezüglich des solothurnischen Untersuchungsrichters) im Fall H. B. bestätigt und präzisiert. Nach der Rechtsprechung des EGMR kann es nicht darauf ankommen, ob der haftanordnende Untersuchungsrichter in der Folge tatsächlich Anklagefunktionen ausübt, welche Gerichtsinstanz im Zeitpunkt der allfälligen Anklageerhebung zuständig ist und wer dort tatsächlich die Anklage vertritt. Falls im Zeitpunkt der Haftanordnung der spätere Erlass einer Schluss- bzw. Überweisungsverfügung des Untersuchungsrichters in Frage kommt, welche die faktische Bedeutung einer Anklageschrift hat, darf dieser Untersuchungsrichter in der gleichen Sache nicht als haftanordnender Magistrat tätig sein (EGMR vom 5. April 2001 i.S. H. B. c. CH, a.a.O., Ziff. 58-63). Ob der Untersuchungsrichter bei seiner Haftanordnung weisungsgebunden war und ob er oder die Staatsanwaltschaft später allenfalls die Anklage vor dem zuständigen Gericht erhebt, ist nach der Auffassung des EGMR nicht massgeblich (EGMR i.S. H. B., a.a.O., Ziff. 62-63). Da eine entsprechende Überweisungs- und Schlussverfügung des Untersuchungsrichters im Zeitpunkt der Haftanordnung nicht ausgeschlossen werden konnte, erkannte der EGMR im Fall H. B. auf eine Verletzung von Art. 5 Ziff. 3 EMRK durch die Schweiz.
2.4 Der Wortlaut des am 1. Januar 2000 in Kraft getretenen <ref-law> geht über Art. 5 Ziff. 3 EMRK hinaus. Die neue Bundesverfassung verlangt, dass der Inhaftierte "unverzüglich einer Richterin oder einem Richter vorgeführt" werden muss (vgl. <ref-ruling> E. 3b S. 173). Damit hat der Verfassungsgesetzgeber die Haftanordnung nach <ref-law> (und nicht bloss die Haftprüfung nach <ref-law>) ausdrücklich in die Hände des Haftrichters bzw. einer unabhängigen richterlichen Behörde gelegt. Ein weisungsgebundener Untersuchungsrichter erfüllt diese Voraussetzungen grundsätzlich nicht (vgl. Andreas Keller, Untersuchungshaft im Kanton St. Gallen - vom alten zum neuen Strafprozessgesetz, AJP 2000, S. 936 ff., 944; Jörg Paul Müller, Grundrechte in der Schweiz: im Rahmen der Bundesverfassung von 1999, der UNO-Pakte und der EMRK, 3. Aufl., Bern 1999, S. 585; Hans Vest, in: Ehrenzeller/Mastronardi/Schweizer/ Vallender [Hrsg.], Die Schweizerische Bundesverfassung, Kommentar, Zürich 2002, Art. 31 N. 24). In der Lehre wird denn auch ausdrücklich darauf hingewiesen, dass diejenigen Kantone - genannt wird unter anderen der Kanton Luzern - bei denen noch Untersuchungsrichter als haftanordnende Magistraten fungieren, ihre Praxis und Gesetzgebung entsprechend anzupassen hätten (vgl. Vest, a.a.O., N. 24). Auch der Entwurf des Eidgenössischen Justiz- und Polizeidepartementes von 2001 für eine schweizerische Strafprozessordnung (VE/StPO) sieht als haftanordnende Behörde eine richterliche Instanz (Zwangsmassnahmengericht) vor (vgl. Art. 235 Abs. 3 und Art. 237 f. VE/StPO).
2.5 Der luzernische Amtsstatthalter erfüllt im Strafprozess Untersuchungs- und teilweise auch Anklagefunktionen und hat grundsätzlich den Weisungen der Staatsanwaltschaft bzw. der hierarchisch übergeordneten Regierungs- und Verwaltungsinstanzen Folge zu leisten (vgl. dazu ausführlich oben, E. 2.2). Es fragt sich, ob <ref-law> in der Weise ausgelegt werden könnte, dass (unter den Voraussetzungen der bisherigen Praxis zu Art. 5 Ziff. 3 EMRK) nach wie vor auch Untersuchungsrichter ausnahmsweise als haftanordnende Magistraten walten könnten. Die Frage kann im vorliegenden Fall offen bleiben, da auch die Voraussetzungen der dargelegten Rechtsprechung zu Art. 5 Ziff. 3 EMRK (personelle Funktionenteilung) nicht erfüllt wären. Unbestrittenermassen hat hier der gleiche Amtsstatthalter die Haft angeordnet, die Untersuchung geführt, die Strafverfügung vom 13. September 2004 erlassen und die Strafsache (nach unterbliebener Annahme der Strafverfügung durch den Angeschuldigten) anschliessend an das Amtsgericht Luzern-Stadt überwiesen. Der Einwand, dass eine allfällige persönliche Anklagevertretung vor Gericht und vor den Rechtsmittelinstanzen jeweils grundsätzlich durch die Staatsanwaltschaft als strafprozessuale Partei zu erfolgen hätte, vermag daran nichts zu ändern. Dies umso weniger, als die Staatsanwaltschaft gerade in kleineren Straffällen vor unterinstanzlichen Gerichten nur äusserst selten persönlich die Anklage vertritt. Die Luzerner Staatsanwaltschaft räumt selbst ausdrücklich ein, dass "der Staatsanwalt vor Amtsgericht sehr selten persönlich auftritt oder schriftlich Stellung nimmt". Eine separate Anklageschrift des Staatsanwaltes erfolgt grundsätzlich nur bei kriminalgerichtlicher Zuständigkeit. In den anderen Fällen bildet das Überweisungserkanntnis bzw. die Strafverfügung des Amtsstatthalters die Anklageschrift (vgl. § 158 Abs. 1 i.V.m. §§ 129 und 173 Abs. 1 StPO/LU).
Entscheidend ist hier, dass der die Haft anordnende Amtsstatthalter angesichts seiner Untersuchung, der Ausfällung seiner Strafverfügung und der anschliessenden Überweisung der Strafverfügung an das Strafgericht in der gleichen Strafsache mit Untersuchungs- und Anklagefunktionen betraut war. Die kantonalen Behörden bestreiten denn auch mit Recht nicht, dass der überwiesenen motivierten Strafverfügung des Amtsstatthalters die Funktion der Anklageschrift zukommt (welche angesichts des Anklagegrundsatzes obligatorisch ist) bzw. dass aufgrund der amtsgerichtlichen Zuständigkeit keine gesonderte Anklageschrift seitens der Staatsanwaltschaft erfolgt. Ist das Amtsgericht zuständig, stellt der Amtsstatthalter den "schriftlichen Antrag über Schuld, Strafe und Massnahmen" (<ref-law>/LU; s. auch §§ 126, 127 Abs. 1 Ziff. 2, 131 Abs. 1, 132 Ziff. 2 und 133ter Abs. 1 StPO/LU). Das Verlesen der "Anträge des Amtsstatthalters oder des Staatsanwaltes" durch den Gerichtspräsidenten gilt gemäss <ref-law>/ LU als "Eröffnung der Anklage".
Nach der dargelegten Praxis des EGMR wäre eine Haftanordnung bereits EMRK-widrig, wenn in der Folge der Erlass einer Überweisungsverfügung mit Anklagefunktion durch den haftanordnenden Magistraten möglich erscheint (vgl. oben, E. 2.3). Dass ein haftanordnender Magistrat nicht zugleich Anklagefunktionen ausüben kann, ergibt sich im Übrigen auch direkt aus dem luzernischen Strafprozessrecht: Für den Fall, dass ein Staatsanwalt strafprozessuale Haft angeordnet bzw. einen Strafbefehl erlassen hat, bestimmt <ref-law>/LU ausdrücklich, dass "die Anklage nicht durch den gleichen Staatsanwalt erhoben werden" darf. Analoges muss nach der dargelegten Lehre und Praxis auch für den Amtsstatthalter gelten, soweit er gerichtliche Überweisungen mit Anklagefunktion vornimmt.
2.6 Schliesslich bleibt noch zu prüfen, ob allenfalls der angefochtene Entscheid des Obergerichtes als ausreichende richterliche Haftanordnung angesehen werden könnte. <ref-law> verlangt, dass eine in Untersuchungshaft versetzte Person "unverzüglich einer Richterin oder einem Richter vorgeführt" werden muss. Namentlich ist es zulässig, dass eine Polizei- oder Untersuchungsbehörde dem Haftrichter einen Antrag auf Haftanordnung stellt, worauf der Haftrichter über den Antrag befindet. Allerdings muss der die Haft anordnende Richter seinen Entscheid "unverzüglich" im Sinne von <ref-law> fällen. Nach herrschender Lehre und Praxis heisst das, grundsätzlich innert ca. 24 bis 48 Stunden (vgl. <ref-ruling> E. 7a S. 232, E. 7c S. 235 mit Hinweisen; Marc Forster, Die Rechte der Inhaftierten - Neue Entwicklungen in der Gesetzgebung und Rechtsprechung, in: Franz Riklin [Hrsg.], Von der Verhaftung bis zum Vollzug - Grenzen der staatlichen Gewalt, Luzern 2004, S. 53 ff., 61 f.; Haefliger/Schürmann, a.a.O., S. 110; Vest, a.a.O., N. 25; vgl. auch Art. 232 Abs. 3 i.V.m. Art. 235 Abs. 3 VE/StPO). Im vorliegenden Fall kann die Verfügung des Amtsstatthalters vom 18. August 2004 nicht als blosser Haftantrag interpretiert werden, zumal das Obergericht die Verfügung erst 13 Tage später, nämlich mit Entscheid vom 31. August 2004, bestätigt hat. Das Obergericht hat somit nicht als haftanordnende Behörde entschieden, sondern als Haftprüfungsinstanz (im Sinne von <ref-law>).
2.7 Im vorliegenden Fall hat keine unverzügliche Vorführung des Inhaftierten vor eine Richterin oder einen Richter stattgefunden. Die Rüge der Verletzung von <ref-law> erweist sich daher als begründet. Insofern ist die Beschwerde gutzuheissen und der angefochtene Entscheid aufzuheben. Die kantonalen Behörden haben im Haftanordnungsverfahren (und im Rahmen der damit verbundenen Neuüberprüfung der Haft betreffend Haftgründe und Haftdauer) dem Anspruch des Beschwerdeführers auf unverzügliche Vorführung vor einen Haftrichter Rechnung zu tragen.
3. Der Beschwerdeführer stellt vor Bundesgericht ein Haftentlassungsgesuch. Dieses ist im Lichte der erhobenen materiellen Vorbringen zu prüfen. Dass im hier zu beurteilenden Fall ein Verfahrensmangel vorliegt, indem der Beschwerdeführer nicht unverzüglich einem Haftrichter im Sinne von <ref-law> vorgeführt wurde, führt nicht automatisch zur Haftentlassung.
3.1 Nach luzernischem Strafprozessrecht kann Untersuchungshaft angeordnet werden, wenn der Angeschuldigte eines Verbrechens oder Vergehens dringend verdächtig ist und zudem ein besonderer Haftgrund besteht, nämlich Fluchtgefahr, "mangelnder Ausweis über die Identität", Kollusionsgefahr oder Wiederholungsgefahr (<ref-law>/LU). Wiederholungsgefahr ist gegeben, wenn "konkrete Hinweise für die Annahme" vorliegen, "dass der Angeschuldigte weitere strafbare Handlungen begehen werde" (<ref-law>/LU). Der Verhaftete ist freizulassen, sobald kein Haftgrund mehr besteht oder wenn die Dauer der Untersuchungshaft im Hinblick auf die zu erwartende Strafe oder Massnahme unverhältnismässig wäre (<ref-law>/LU).
Der Beschwerdeführer bestreitet den dringenden Tatverdacht der Widerhandlung gegen das ANAG nicht. Er wendet sich jedoch gegen die Annahme von Wiederholungsgefahr. Die Gefahr des weiteren Delinquierens sei "nicht offenkundig". Da er über keine Ausreisepapiere verfüge, sei ihm bisher nichts anderes übrig geblieben, als in der Schweiz zu verbleiben. Bei der diplomatischen Vertretung seines Heimatstaates habe er sich vergeblich um Reisedokumente bemüht. Das kantonale Migrationsamt habe ihn dabei zu wenig unterstützt. "Angesichts der Gesamtumstände" sei zudem "nicht ersichtlich", weshalb der Haftzweck nicht auch mit einer milderen Ersatzmassnahme erreicht werden könnte.
3.2 Nach der Praxis des Bundesgerichtes kann die Anordnung von Haft wegen Fortsetzungsgefahr dem strafprozessualen Ziel der Beschleunigung dienen, indem verhindert wird, dass sich das Verfahren durch immer neue Delikte kompliziert und in die Länge zieht (<ref-ruling> E. 3c S. 31). Auch die Wahrung des Interesses an der Verhütung weiterer Delikte ist nicht verfassungs- und grundrechtswidrig. Vielmehr anerkennt Art. 5 Ziff. 1 lit. c EMRK ausdrücklich die Notwendigkeit, Angeschuldigte an der Begehung strafbarer Handlungen zu hindern, somit Spezialprävention, als Haftgrund (<ref-ruling> E. 4c S. 366; <ref-ruling> E. 2c S. 270).
Bei der Annahme, dass Angeschuldigte weitere Verbrechen oder Vergehen begehen könnten, ist allerdings Zurückhaltung geboten. Da Präventivhaft einen schwerwiegenden Eingriff in das Recht der persönlichen Freiheit darstellt, muss sie auf einer hinreichenden gesetzlichen Grundlage beruhen, im öffentlichen Interesse liegen und verhältnismässig sein (<ref-ruling> E. 4 S. 226). Die Aufrechterhaltung von strafprozessualer Haft wegen Fortsetzungsgefahr ist verhältnismässig, wenn einerseits die Rückfallprognose sehr ungünstig und anderseits die zu befürchtenden Delikte von schwerer Natur sind (BGE <ref-ruling> E. 2e S. 271 ff.). Die rein hypothetische Möglichkeit der Verübung weiterer Delikte sowie die Wahrscheinlichkeit, dass nur geringfügige Straftaten verübt werden, reichen dagegen nicht aus, um eine Präventivhaft zu begründen. Schliesslich gilt auch bei der Präventivhaft - wie bei den übrigen Haftarten - dass sie nur als "ultima ratio" angeordnet oder aufrecht erhalten werden darf. Wo sie durch mildere Massnahmen (wie z.B. ambulante ärztliche Betreuung, regelmässige Meldung bei einer Amtsstelle etc.) ersetzt werden kann, muss von der Anordnung oder Fortdauer der Haft abgesehen und an ihrer Stelle eine dieser Ersatzmassnahmen angeordnet werden (<ref-ruling> E. 3a S.62; <ref-ruling> E. 5 S. 213; <ref-ruling> E. 2c S. 270 f.).
3.3 Der Beschwerdeführer räumt ein, dass er bereits im Februar 2003 und Juni 2004 je wegen Verstössen gegen das ANAG bzw. illegalen Aufenthaltes in der Schweiz rechtskräftig zu Gefängnisstrafen verurteilt worden ist. Am 17. August 2004 sei er erneut wegen illegalen Aufenthaltes im Bahnhof Luzern polizeilich verhaftet und anschliessend in Untersuchungshaft versetzt worden. Das Amtsstatthalteramt Luzern-Stadt hat am 13. September 2004 deswegen eine Strafverfügung wegen rechtswidrigen Aufenthalts (Art. 23 Abs. 1 al. 4 ANAG) erlassen. Nach unterbliebener Annahme der Strafverfügung wurde die Strafsache an das Amtsgericht Luzern-Stadt überwiesen.
Damit ist unbestritten, dass der Beschwerdeführer bereits mehrmals wegen einschlägigen Vergehen strafrechtlich verurteilt wurde. Dennoch musste im August 2004 ein neuerliches Strafverfahren wegen illegalen Aufenthalts gegen ihn eingeleitet werden. Damit erscheint die Annahme von Wiederholungsgefahr im Sinne von <ref-law>/LU beim aktuellen Verfahrensstand grundsätzlich als verfassungskonform. Der Auffassung des Beschwerdeführers, das "allfällige Delikt" des jahrelangen illegalen Aufenthalts habe "für die Allgemeinheit und die öffentliche Sicherheit keine schwerwiegenden Folgen", kann nicht beigepflichtet werden.
3.4 Der Beschwerdeführer wendet ein, er sei Ende Juni 1998 in die Schweiz eingereist und habe ein Asylgesuch gestellt, das in der Folge rechtskräftig abgelehnt worden sei. Anschliessend habe er mehrmals versucht, "von der heimatlichen diplomatischen Vertretung (Vertretung von Buthan in Genf) Reisedokumente zu erhalten, damit er in seine Heimat reisen kann". "Trotz dieser Bemühungen" habe er jedoch nie Reisedokumente bekommen, weshalb er weder in seine Heimat, noch in einen Drittstaat legal habe ausreisen können. Das kantonale Migrationsamt habe ihn dabei zu wenig unterstützt.
Diese Vorbringen sind primär verwaltungs- und ausländerrechtlicher Natur. Grundsätzlich ist es Sache des von einem rechtskräftigen Wegweisungsentscheid betroffenen Ausländers, die für die Ausreise in sein Heimatland oder in einen Drittstaat notwendigen Papiere bei der zuständigen diplomatischen Vertretung seines Heimatstaates zu beschaffen. Nötigenfalls kann er auch die Behörden seines Aufenthaltsortes um Mithilfe bei der Beschaffung der benötigten Dokumente ersuchen. Bei Zweifeln an der Identität und an der Staatsangehörigkeit hat der Betroffene ausserdem die Fremdenpolizeibehörde bei der Beschaffung der Dokumente bzw. bei der Identitätsabklärung zu unterstützen. Nach der Praxis des luzernischen Amtes für Migration gelangt dieses bei kooperativem Verhalten eines weggewiesenen Ausländers mit einem Gesuch um Vollzugsunterstützung bzw. Beschaffung von Ersatzreisedokumenten an das EJPD. Ein solches Vorgehen setze allerdings voraus, dass der Weggewiesene korrekte und vollständige Angaben zu seiner Identität macht.
3.5 Der Beschwerdeführer behauptet, er sei Staatsangehöriger Bhutans. Zwar legt er ein Schreiben an die diplomatische Vertretung Bhutans vor, das vom 13. September 2004 datiert. Dem Standpunkt, es sei ihm nichts anderes übrig geblieben, als sich trotz rechtskräftigen Wegweisungsentscheides und mehrmaliger einschlägiger strafrechtlicher Verurteilungen jahrelang illegal in der Schweiz aufzuhalten, kann jedoch nicht gefolgt werden. Gemäss bei den Akten liegenden widersprüchlichen Aussagen des Beschwerdeführers sei er in der Schweiz geblieben, weil ihm sein Anwalt dazu geraten habe. Er habe in der Schweiz eine Gefängnisstrafe zu verbüssen; ausserdem sei er krank und brauche eine Operation. Die Staatsangehörigkeit und die Identität des Beschwerdeführers erscheinen nach den vorliegenden Akten keineswegs geklärt; ausserdem weigert er sich konsequent, bei der Klärung seiner wahren Identität und der Beschaffung von Ersatzreisedokumenten mitzuwirken. Laut Strafanzeige des Amtes für Migration des Kantons Luzern vom 7. März 2003 stehe "für die schweizerischen Behörden fest, dass X._ nicht aus Bhutan stammt". Dennoch halte der Beschwerdeführer "an seinen Personalien fest" und sei "einen Beweis dafür bis heute schuldig geblieben". Er verheimliche "seine wahre Identität nach wie vor". Gegenüber der Fremdenpolizei habe er jahrelang behauptet, seine Papiere würden "demnächst" eintreffen; dies sei als "Verzögerungstaktik" einzustufen.
3.6 Wie sich aus den Akten der früheren Strafverfahren ergibt, hat das Amtsgericht Luzern-Stadt das kantonale Migrationsamt mit Schreiben vom 11. März 2004 eingeladen, zu folgenden Fragen Stellung zu nehmen: "Hat Herr X._ das AMIGRA" (Migrationsamt) "je ersucht, ihm bei der Beschaffung von Ausreisepapieren behilflich zu sein?" "Hat das AMIGRA Anstrengungen unternommen, um für Herrn X._ Ausreisepapiere (...) zu beschaffen?" "Hat der Angeklagte mit dem AMIGRA kooperiert?" In seiner Stellungnahme vom 15. März 2004 äusserte sich das Migrationsamt dazu wie folgt: "X._ hat uns nie ersucht, bei der Beschaffung heimatlicher Ausweispapiere behilflich zu sein. Er gab jedoch wiederholt vor, selber Papiere aus Bhutan beschaffen zu wollen, solche hat er jedoch bis heute keine abgegeben. Da er offensichtlich nicht aus Bhutan stammt, kann ausgeschlossen werden, dass er je welche beschaffen wird. Es handelt sich bei seinen angeblichen Bemühungen offensichtlich um eine Verzögerungstaktik". Sollte er das AMIGRA darum ersuchen, ihm bei der Beschaffung von Ausweispapieren behilflich zu sein, sei nicht ersichtlich, "wie wir ihm helfen könnten, solange er unkooperativ ist bzw. seine wahre Identität und Herkunft verheimlicht". Das Migrationsamt habe bereits im Jahre 2000 "vom Amtes wegen versucht, ein Reisepapier für X._ zu beschaffen, indem wir am 17. März 2000 ein entsprechendes Gesuch an die Botschaft von Bhutan stellten. Dieses Gesuch wurde am 23. März 2000 negativ beantwortet. Diese Ablehnung war voraussehbar, da wir keine Identitätsdokumente von X._ besitzen und bereits wussten, dass er eine falsche Identität/Herkunft verwendet bzw. nicht von Bhutan stammt". "Auf Gesuche bei den nepalischen und indischen Behörden haben wir bis jetzt verzichtet, da dies aussichtslos ist, solange X._ an seiner falschen Identität/Herkunft festhält. Selbstverständlich wurden die Gesuche des X._ an die nepalische und indische Vertretung negativ beschieden, hielt er dabei doch an seiner bhutanesischen Herkunft fest. Sein Schreiben an die Botschaft von Bhutan muss als Sabotageakt gewertet werden; er versuchte darin offensichtlich, eine Reisepapierausstellung zu verhindern". "Er wies nämlich darauf hin, dass er Asylsuchender aus Bhutan sei (womit er unnötig die Botschaft gegen sich aufbringt), dass wir ihn zur Reisepapierbeschaffung aufforderten, obwohl seine Asylbeschwerde gutgeheissen wurde und dass ihm von der Botschaft bereits gesagt wurde, dass er keine Papiere erhalten könne". "Am 19.04.2000 ersuchten wir das Bundesamt für Flüchtlinge (BFF) um Vollzugsunterstützung. Solange jedoch X._ seine wahre Identität und Herkunft verschleiert und nicht bereit ist, bei der Beschaffung heimatlicher Papiere mitzuarbeiten bzw. die Identität und Herkunft nicht nachgewiesen werden kann, können auch seitens des BFF derzeit keine Reisepapiere für ihn beschafft werden". "X._ kooperiert insoweit, als er nicht untertaucht (und deshalb auch von den Fürsorgebehörden unterstützt werden muss) und sich zu unserer Verfügung hält bzw. den meisten Vorladungen und Meldepflichten bisher Folge leistete. Sobald es um Reisepapierbeschaffung bzw. Offenlegung seiner wahren Identität und Herkunft zwecks Beschaffung heimatlicher Reisepapiere geht, war X._bisher noch nie kooperationsbereit". "X._ wurde bereits beim Einreichen des Asylgesuches im Juni 1998 aufgefordert, heimatliche Dokumente zu beschaffen. Nach fast 6 Jahren warten wir immer noch auf diese. Am 21.01.2000 (!) wurde er aufgefordert, sofort auszureisen und befindet sich seither illegal in der Schweiz. Unsere Möglichkeiten zur Reisepapierbeschaffung sind erschöpft". "X._ liess sich trotz unseren bisherigen intensiven Bemühungen (...) nicht zur Kooperation bewegen, weshalb wir gezwungen waren, ihn wegen illegalem Aufenthalt sowie Angaben falscher Personalien anzuzeigen".
3.7 Aufgrund der vorliegenden Akten erscheint das Vorbringen, der Beschwerdeführer habe sich zuvor jahrelang vergeblich um Reisepapiere bemüht, als blosse Schutzbehauptung. Er hält sich seit Jahren illegal in der Schweiz auf und weigert sich bisher trotz intensiver Bemühungen der Migrationsbehörde systematisch, zur Abklärung seiner Identität und damit zur Beschaffung von Ersatzreisedokumenten beizutragen. Dadurch erschwert und behindert der Beschwerdeführer nicht nur seine rechtskräftig angeordnete Wegweisung, sondern auch die eingeleiteten Strafverfahren. Insbesondere trägt sein Verhalten dazu bei, dass sich das Verfahren kompliziert und in die Länge zieht (vgl. <ref-ruling> E. 3c S. 31). Im vorliegenden konkreten Fall kann auch nicht mehr von Bagatellvorwürfen gesprochen werden, weshalb der Haftgrund der Wiederholungsgefahr zu bejahen ist.
Im Übrigen nennt die Luzerner Strafprozessordnung neben Wiederholungsgefahr auch noch den "mangelnden Ausweis über die Identität" als besonderen Haftgrund (<ref-law>/LU). Fragen materiellstrafrechtlicher Natur werden in der Beschwerde nicht aufgeworfen. Dies gilt namentlich für die strafrechtliche Problematik des Zustands- und Dauerdeliktes, die Frage einer allfälligen entschuldigenden Pflichtenkollision oder für die Abgrenzung der strafrechtlichen Sanktionen von den fremdenpolizeilichen Zwangsmassnahmen (namentlich Ausschaffungshaft). Solche materiellrechtlichen Fragen wären denn auch grundsätzlich durch den zuständigen Strafrichter zu prüfen und nicht durch das Bundesgericht im vorliegenden Haftbeschwerdeverfahren.
3.8 Nach dem Gesagten liegen beim jetzigen Verfahrensstand ausreichende strafprozessuale Haftgründe vor, und es rechtfertigt sich keine sofortige Haftentlassung durch das Bundesgericht.
Bei dieser Sachlage ist das Haftentlassungsgesuch des Beschwerdeführers abzuweisen. Die übrigen angerufenen Grundrechtsbestimmungen (namentlich Grundsatz von Treu und Glauben, Menschenwürde, Rechtsgleichheit, Willkürverbot, Grundsatz des "fair trial" oder Diskriminierungsverbot) haben im vorliegenden Zusammenhang keine über das bereits Dargelegte hinausgehende selbstständige Tragweite.
4. Zusammenfassend ergibt sich, dass die Beschwerde teilweise gutzuheissen und der angefochtene Entscheid aufzuheben ist. Die kantonalen Behörden haben im Haftanordnungsverfahren dem Anspruch des Beschwerdeführers auf unverzügliche Vorführung vor einen Haftrichter (<ref-law>) Rechnung zu tragen. Es hat eine rasche Neuüberprüfung der Haft (betreffend Haftgründe und Haftdauer) zu erfolgen. Dabei ist auch der Gesichtspunkt der Verhältnismässigkeit zu prüfen und für eine Koordination des Falles mit der kantonalen Fremdenpolizeibehörde zu sorgen. Da der angefochtene Entscheid aufzuheben ist, kann auch die Neufestsetzung des Kostendispositivs des angefochtenen Entscheides den kantonalen Instanzen überlassen werden. Das vor Bundesgericht erhobene Haftentlassungsgesuch ist beim heutigen Verfahrensstand abzuweisen.
Nachdem der Beschwerdeführer im Verfahren vor Bundesgericht weitgehend obsiegt, ist ihm eine Parteientschädigung nach Art. 159 OG zuzusprechen. Er hat ein Gesuch um unentgeltliche Rechtspflege gestellt (Art. 152 OG). Grundsätzlich (und soweit notwendig) wurde die unentgeltliche Rechtspflege mit Beschluss des Bundesgerichtes vom 19. Oktober 2004 vorsorglich bewilligt, und der Rechtsvertreter des Beschwerdeführers wurde als unentgeltlicher Rechtsbeistand ernannt. Die Festlegung des Verteidigerhonorars wurde dem vorliegenden Endurteil vorbehalten.
Bei diesem Prozessausgang sind keine Gerichtskosten zu erheben (Art. 152 Abs. 1 und Art. 156 Abs. 1-3 OG). Dem in Rechnung gestellten Aufwand entsprechend und unter Berücksichtigung der bundesgerichtlichen Praxis wird dem Beschwerdeführer zu Lasten des Kantons Luzern eine Parteientschädigung von pauschal Fr. 3'500.-- zugesprochen (Art. 159 Abs. 1 OG). Das bereits bewilligte Gesuch um unentgeltliche Rechtspflege kommt daher nicht zum Tragen.

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird teilweise gutgeheissen, und der angefochtene Entscheid des Obergerichts des Kantons Luzern, II. Kammer, vom 31. August 2004 wird aufgehoben.
2. Das Haftentlassungsgesuch wird abgewiesen.
3. Es werden keine Kosten erhoben.
4. Der Kanton Luzern hat dem Beschwerdeführer eine Parteientschädigung von Fr. 3'500.-- zu entrichten.
5. Dieses Urteil wird dem Beschwerdeführer, dem Amtsstatthalteramt Luzern-Stadt sowie der Staatsanwaltschaft und dem Obergericht, II. Kammer, des Kantons Luzern schriftlich mitgeteilt.
Lausanne, 2. November 2004
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: