Sachverhalt: A. X._ (geb. 1975) ist vietnamesischer Staatsbürger chinesischer Abstammung. Er kam 1991 als Kontingentsflüchtling in die Schweiz, wo ihm am 5. Juli 1991 Asyl gewährt wurde. Zuvor waren seine Familie und er nach Malaysia geflohen und hatten sich dort längere Zeit in einem Lager aufgehalten. Am 20./21. Mai 2002 beging X._ mit Landsleuten in Bern einen Raub, in dessen Verlauf zwei Personen ums Leben kamen. Das Obergericht des Kantons Bern verurteilte ihn am 17. November 2006 wegen Raubes (unter Offenbarung besonderer Gefährlichkeit [Art. 140 Abs. 3 StGB]) sowie (mittäterschaftlich) begangenen mehrfachen Mordes (Art. 112 StGB) zu 15 Jahren Zuchthaus sowie 12 Jahren Landesverweisung. Das Bundesgericht bestätigte diesen Entscheid am 17. Mai 2007 (Urteil 6P.19/2007 und 6S.51/2007 vom 17. Mai 2007). Am 15. August 2007 wies das Sicherheitsdepartement des Kantons Basel-Stadt X._ aus der Schweiz aus. Am 6. Februar 2009 widerrief das Bundesamt für Migration das Asyl, wogegen X._ erfolglos an das Bundesverwaltungsgericht gelangte. Dieses hielt in seinem Urteil vom 17. September 2010 fest, dass die Aberkennung des Asyls nicht automatisch auch die Aberkennung der Flüchtlingseigenschaft nach sich ziehe; der Verlust des Asyls wirke sich für den Betroffenen deshalb nicht unmittelbar und konkret nachteilig aus, insbesondere könne er sich weiterhin in der Schweiz aufhalten und arbeiten. B. Am 29. Juni 2012 ist X._ nach Verbüssung von zwei Dritteln seiner Freiheitsstrafe bedingt aus dem Strafvollzug entlassen worden. Das Migrationsamt des Kantons Basel-Stadt nahm ihn am gleichen Tag für drei Monate in Ausschaffungshaft. Der Einzelrichter für Zwangsmassnahmen am Appellationsgericht des Kantons Basel-Stadt bestätigte diese am 29. Juni 2012. Er verwarf die Einwände von X._, dem Vollzug der Ausweisung stünden das Rückschiebungsverbot und sein Flüchtlingsstatus entgegen. Dabei stellte er auf einen Amtsbericht des Bundesamts für Migration (BFM) vom 18. Juni 2012 ab, der zum Schluss gekommen war, dass sich X._ wegen seiner besonderen Gefährlichkeit nicht auf das Rückschiebungsverbot berufen könne (Art. 5 Abs. 2 AsylG [SR 142.31]; Art. 33 Abs. 2 Flüchtlingskonvention [FK; SR 0.142.30]; Art. 3 EMRK; vgl. BGE 135 II 110 ff.) bzw. ihm heute in seiner Heimat keine Verfolgung mehr drohe. C. X._ beantragt mit Eingabe vom 2. August 2012, den Entscheid des Haftrichters am Appellationsgericht des Kantons Basel-Stadt aufzuheben; er sei sofort aus der Ausschaffungshaft zu entlassen. Die Ausweisungsverfügung sei nichtig, da im Ausweisungsentscheid vom 15. August 2007 die flüchtlingsrechtliche Problematik überhaupt nicht berücksichtigt worden sei. Im Übrigen fehle es an einem Haftgrund und sei die Ausschaffungshaft unverhältnismässig, da keinerlei Wiederholungsgefahr bestehe; er habe sich seit neun Jahren tadellos verhalten und werde sich den Behörden bei seiner Familie zur Verfügung halten. Das Justiz- und Sicherheitsdepartement und der Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Appellationsgericht des Kantons Basel-Stadt sowie das Bundesamt für Migration beantragen, die Beschwerde abzuweisen und die angeordnete Ausschaffungshaft zu bestätigen. Das Bundesamt weist daraufhin, dass es mit Verfügung vom 16. August 2012 inzwischen die Flüchtlingseigenschaft von X._ aberkannt habe. X._ hat am 23. August 2012 an seinen Anträgen und Ausführungen festgehalten und verschiedene verfahrensrechtliche Anträge gestellt.