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 (Art. 31 Abs. 3 BV), 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.