Sachverhalt: A. Der nach eigenen Angaben aus Guinea-Bissau stammende X._ (geb. 1980) reiste am 27. April 2004 in die Schweiz ein, wo er tags darauf um Asyl nachsuchte. Das Bundesamt für Flüchtlinge trat am 11. Mai 2004 auf sein Gesuch nicht ein, wies ihn weg und hielt ihn an, spätestens am Tag nach Eintritt der Rechtskraft seines Entscheids das Land zu verlassen. Das Bundesamt ging davon aus, X._ habe ohne entschuldbare Gründe nicht innerhalb von 48 Stunden nach Einreichung seines Gesuchs Reisepapiere oder andere Dokumente abgegeben, die es erlauben würden, ihn zu identifizieren; zudem lägen keine Hinweise auf eine Verfolgung vor, die sich nicht als offensichtlich haltlos erwiesen (Art. 32 Abs. 2 lit. a des Asylgesetzes vom 26. Juni 1998, AsylG; SR 142.31). Diese Verfügung erwuchs unangefochten in Rechtskraft. B. Am 27. Mai 2004 wandte sich X._ mit einem Gesuch um Nothilfe (Art. 12 BV) an das Migrationsamt des Kantons Zürich; dabei erklärte er, sich den Behörden in der ihm zugewiesenen Notunterkunft zur Verfügung halten zu wollen. Er wurde gleichentags verhaftet, mit Strafbefehl vom 28. Mai 2004 wegen illegalen Verbleibs in der Schweiz zu 30 Tagen Gefängnis bedingt verurteilt und anschliessend in Ausschaffungshaft genommen. Der Haftrichter am Bezirksgericht Zürich prüfte diese am 29. Mai 2004 und bestätigte sie bis zum 27. August 2004. C. Mit Verwaltungsgerichtsbeschwerde vom 15. Juni 2004 beantragt X._, die Haftgenehmigung sei aufzuheben und er sei aus der Haft zu entlassen. Das Migrationsamt des Kantons Zürich schliesst auf Abweisung der Beschwerde. Der Haftrichter am Bezirksgericht Zürich hat auf eine Vernehmlassung verzichtet. Das Bundesamt für Flüchtlinge liess sich nicht vernehmen. X._ hat am 30. Juni 2004 an seinen Anträgen und Ausführungen festgehalten.