Sachverhalt:
A. X._ (geb. 1957) stammt aus Kambodscha. Am 12. April 1979 erhielt er in der Schweiz Asyl. Seit 1984 verfügt X._ im Kanton Aargau über eine Niederlassungsbewilligung. Von 1981 bis anfangs 2006 war er mit der malaysischen Staatsangehörigen Y._ (geb. 1960) verheiratet. Der Ehe entstammen zwei - inzwischen volljährige - Kinder (A._, geb. 1982, und B._, geb. 1986); zudem nahm das Ehepaar 1990 ein weiteres Kind zur Pflege auf (C._, geb. 1988).
B. Am 9. Oktober 1997 wurde X._ wegen einfacher Körperverletzung und Sachbeschädigung zu einer Busse von Fr. 400.-- und am 9. Mai 2001 wegen Betrugs und Diebstahls (begangen am 3. Mai 2000) zu einer bedingten Gefängnisstrafe von drei Monaten (bei einer Probezeit von drei Jahren) verurteilt. Am 26. September 2001 gab X._ mehrere Schüsse in die Decke, in eine Glasvitrine und von aussen in die Fensterfront eines Zürcher Lokals ab. Das Geschworenengericht des Kantons Zürich sprach ihn am 28. Januar 2004 im Zusammenhang hiermit der Gefährdung des Lebens, der mehrfachen untauglich versuchten Gefährdung des Lebens sowie des mehrfachen Vergehens gegen das Waffengesetz für schuldig und verurteilte ihn zu einer Zuchthausstrafe von 4 1⁄2 Jahren; gleichzeitig erklärte es die bedingte Gefängnisstrafe von 3 Monaten für vollziehbar. Am 22. April 2005 wurde X._ bedingt aus dem Strafvollzug entlassen.
C. C.a Das Bundesamt für Flüchtlinge (BFF) widerrief am 20. Dezember 2004 das Asyl von X._, da er sich eine "besonders verwerfliche strafbare Handlung" habe zuschulden kommen lassen; der Widerruf des Asyls tangiere seine Flüchtlingseigenschaft nicht, weshalb er weiter in den Genuss der Garantien der Flüchtlingskonvention komme. Im Falle der Wegweisung werde es an der zuständigen kantonalen Behörde sein zu prüfen, ob deren Vollzug zulässig, zumutbar und möglich sei. Mit Urteil vom 14. Januar 2006 wies die Schweizerische Asylrekurskommission die hiergegen eingereichte Beschwerde ab: X._ habe, obwohl er von der Anklage der versuchten vorsätzlichen Tötung freigesprochen worden sei, erheblich und in "besonders verwerflicher Weise" gegen die hiesige Rechtsordnung verstossen. Der Entzug seines Asyls sei nicht unverhältnismässig, da er "als vorläufig aufgenommener Flüchtling alle Rechte gemäss Flüchtlingskonvention" bewahre.
C.b Am 20. August 2007 wies das Migrationsamt des Kantons Aargau X._ auf unbestimmte Dauer aus der Schweiz aus; er habe das Land zu verlassen, "sobald der Vollzug möglich und zumutbar" erscheine. Zwar befinde sich X._ bereits seit über 25 Jahren in der Schweiz, doch sei er hier schwer straffällig geworden; er habe "aus absolut nichtigem Anlass ein skrupelloses Handeln an den Tag gelegt und ohne zu zögern auf verschiedene gänzlich unbeteiligte Personen geschossen, wobei es nicht sein Verdienst" gewesen sei, dass dabei "niemand verletzt oder gar getötet" worden sei. Seine Flüchtlingseigenschaft bestehe fort; der Vollzug der Ausweisung erscheine unzulässig, da eine Anfrage beim Bundesamt für Migration "keine Klarheit darüber gebracht" habe, "ob der Betroffene ohne Verletzung" der flüchtlingsrechtlichen Grundlagen "in sein Heimatland ausgeschafft werden" könne; "Ausnahmen vom Rückschiebungsverbot (Gefährdete Sicherheit der Schweiz, Gemeingefährlichkeit)" seien "nicht vorhanden". Der Rechtsdienst des Migrationsamts bestätigte diesen Entscheid auf Einsprache hin am 27. März 2008: Mit dem Widerruf des Asyls sei "eine flüchtlings- bzw. asylrechtliche Schranke" für die Ausweisung "entfallen"; über die Vollziehbarkeit der Massnahme bedürfe es keines abschliessenden Befunds, da die Asylbehörden X._ den Status eines vorläufig aufgenommenen Flüchtlings belassen hätten.
C.c X._ gelangte hiergegen erfolglos an das Rekursgericht im Ausländerrecht des Kantons Aargau. Dieses hielt in seinem Urteil vom 22. August 2008 fest, dass unter Berücksichtigung der gesamten Umstände das "sehr grosse" öffentliche Interesse an der Ausweisung von X._ sein privates an einem weiteren Verbleib in der Schweiz überwiege. Nachdem das Migrationsamt lediglich die Ausweisung verfügt, jedoch auf den Vollzug der Ausweisung verzichtet habe und dem Bundesamt für Migration die vorläufige Aufnahme beantragen werde, sei nur zu prüfen, ob die Ausweisung und der damit verbundene Verlust der Niederlassungsbewilligung als verhältnismässig gelten könne; alle Aspekte, die das private Interesse erhöhten, weil die Rückkehr von X._ aufgrund der aktuellen Situation in seinem Heimatland unzumutbar sei, könnten ausser Acht gelassen werden; diesen Aspekten werde bereits mit der geplanten vorläufigen Aufnahme Rechnung getragen.
D. X._ beantragt mit Eingabe vom 30. September 2008, das Urteil des Rekursgerichts im Ausländerrecht aufzuheben und auf seine Ausweisung zu verzichten. Er macht geltend, die Interessenabwägung der Vorinstanz sei unvollständig und rechtswidrig. Das Rekursgericht habe seine Interessen zu einem wesentlichen Teil nicht berücksichtigt, indem es die Umstände ausgeblendet habe, die seiner Ausreise nach Kambodscha entgegenstünden. Wegen des fehlenden Rückfallrisikos sei das öffentliche Interesse an seiner Fernhaltung "nicht mehr allzu gross"; die Vorinstanz bejahe die Verhältnismässigkeit der ausländerrechtlichen Massnahme letztlich nur deshalb, weil diese nicht vollzogen werden könne und somit gar keine Wirkung entfalten werde.
Das Rekursgericht im Ausländerrecht des Kantons Aargau und das Bundesamt für Migration beantragen, die Beschwerde abzuweisen. Das Migrationsamt des Kantons Aargau hat sich nicht vernehmen lassen.
E. Mit Verfügung vom 28. Oktober 2008 hat der Abteilungspräsident der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt und festgehalten, dass X._ mit Blick auf die von ihm ausgeübte unselbständige Erwerbstätigkeit für die Dauer des bundesgerichtlichen Verfahrens als Niedergelassener zu betrachten sei.

Erwägungen:
1. 1.1 Die Aargauer Behörden haben den Beschwerdeführer, welcher nach wie vor als Flüchtling im Sinne des Abkommens vom 28. Juli 1951 über die Rechtsstellung der Flüchtlinge (Flüchtlingskonvention, FK; SR 0.142.30) gilt, ausländerrechtlich ausgewiesen (Art. 10 Abs. 1 lit. a des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer [ANAG; BS 1 121 ff.] in Verbindung mit Art. 65 des Asylgesetzes vom 26. Juni 1998 [AsylG; SR 142.31]). Gegen entsprechende letztinstanzliche kantonale Gerichtsentscheide ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig (Art. 82 ff.; <ref-ruling> E. 1a S. 2; <ref-ruling> E. 2.1 S. 198). Auf die frist- und formgerecht eingereichte Eingabe des durch das angefochtene Urteil in schutzwürdigen eigenen Interessen betroffenen Beschwerdeführers (<ref-law>) ist einzutreten.
1.2 Seit dem 1. Januar 2008 gilt das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20). Da die umstrittene Ausweisung vor diesem Datum verfügt wurde, ist deren Zulässigkeit in Anwendung des damals geltenden Rechts zu prüfen (Art. 126 Abs. 1 AuG [analog]). Dabei ist auf den von der Vorinstanz ermittelten Sachverhalt abzustellen (<ref-law>). Dieser kann - soweit entscheidwesentlich - nur berichtigt bzw. ergänzt werden, falls er sich als offensichtlich unrichtig erweist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 97 Abs. 1 bzw. <ref-law>). Das Bundesgericht wendet das Recht hingegen von Amtes wegen an (<ref-law>); es ist deshalb weder an die Begründung im angefochtenen Urteil noch an jene der Parteien gebunden. Immerhin prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG; vgl. <ref-ruling> E. 2.1 S. 245 f.), grundsätzlich nur die geltend gemachten Vorbringen, es sei denn, die rechtlichen Mängel erschienen geradezu offensichtlich (<ref-ruling> E. 1.4.1 S. 254).
2. 2.1 Ein Ausländer kann gemäss Art. 10 Abs. 1 lit. a ANAG aus der Schweiz ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft worden ist und die nach Art. 11 Abs. 3 ANAG bzw. allenfalls Art. 8 Ziff. 2 EMRK gebotene Interessenabwägung diese Massnahme nicht als unverhältnismässig erscheinen lässt. Dabei sind namentlich die Schwere des Verschuldens, die Dauer der Anwesenheit sowie die dem Betroffenen und seiner Familie drohenden Nachteile zu berücksichtigen (vgl. Art. 16 Abs. 3 ANAV [SR 142.201]; Urteil des EGMR i.S. Boultif gegen Schweiz vom 2. August 2001, Rz. 48, in: VPB 65/2001 Nr. 138; <ref-ruling> E. 3; <ref-ruling> ff.). Je länger ein Ausländer in der Schweiz lebt, desto strengere Anforderungen sind an die Voraussetzungen seiner Ausweisung zu stellen. Selbst bei einem Ausländer, der bereits hier geboren ist und sein ganzes bisheriges Leben in der Schweiz verbracht hat, ist eine solche bei Gewaltdelikten bzw. wiederholter schwerer Straffälligkeit indessen nicht generell ausgeschlossen (<ref-ruling> E. 4.4.2 S. 190; <ref-ruling> E. 2b S. 523 f.; <ref-ruling> E. 2 und 3 S. 435 ff.). Ausschlaggebend ist die Verhältnismässigkeit der Massnahme im Einzelfall, die praxisgemäss gestützt auf die gesamten wesentlichen Umstände geprüft werden muss (BGE <ref-ruling> E. 2b S. 523 f. mit Hinweis).
2. 2.1 Ein Ausländer kann gemäss Art. 10 Abs. 1 lit. a ANAG aus der Schweiz ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft worden ist und die nach Art. 11 Abs. 3 ANAG bzw. allenfalls Art. 8 Ziff. 2 EMRK gebotene Interessenabwägung diese Massnahme nicht als unverhältnismässig erscheinen lässt. Dabei sind namentlich die Schwere des Verschuldens, die Dauer der Anwesenheit sowie die dem Betroffenen und seiner Familie drohenden Nachteile zu berücksichtigen (vgl. Art. 16 Abs. 3 ANAV [SR 142.201]; Urteil des EGMR i.S. Boultif gegen Schweiz vom 2. August 2001, Rz. 48, in: VPB 65/2001 Nr. 138; <ref-ruling> E. 3; <ref-ruling> ff.). Je länger ein Ausländer in der Schweiz lebt, desto strengere Anforderungen sind an die Voraussetzungen seiner Ausweisung zu stellen. Selbst bei einem Ausländer, der bereits hier geboren ist und sein ganzes bisheriges Leben in der Schweiz verbracht hat, ist eine solche bei Gewaltdelikten bzw. wiederholter schwerer Straffälligkeit indessen nicht generell ausgeschlossen (<ref-ruling> E. 4.4.2 S. 190; <ref-ruling> E. 2b S. 523 f.; <ref-ruling> E. 2 und 3 S. 435 ff.). Ausschlaggebend ist die Verhältnismässigkeit der Massnahme im Einzelfall, die praxisgemäss gestützt auf die gesamten wesentlichen Umstände geprüft werden muss (BGE <ref-ruling> E. 2b S. 523 f. mit Hinweis).
2.2 2.2.1 Ein Flüchtling darf - unter Vorbehalt von <ref-law> (Non-Refoulement-Prinzip, vgl. unten E. 2.2.2) - nur ausgewiesen werden, wenn er die innere oder äussere Sicherheit gefährdet oder die öffentliche Ordnung "in schwerwiegender Weise" verletzt hat (vgl. <ref-law> sowie Art. 32 Ziff. 1 FK; <ref-ruling> E. 3b S. 183; s.a. FELLER/TÜRK/NICHOLSON, La protection des réfugiés en droit international, Brüssel 2008, S. 133 ff.; ZÜND/ARQUINT HILL, in: Uebersax et al., Ausländerrecht, 2. Aufl., Basel 2009, Rz. 8.89 ff.); insofern wird die Möglichkeit seiner Ausweisung flüchtlings- bzw. asylrechtlich beschränkt (Urteile 2A.51/2006 vom 8. Mai 2006 E. 2.2 und 2A.313/2005 vom 25. August 2005 E. 2.2, je mit Hinweisen). Die Flüchtlingseigenschaft wird durch das Bundesamt für Migration aberkannt, wenn die ausländische Person sie durch falsche Angaben oder Verschweigen wesentlicher Tatsachen erschlichen hat oder Gründe im Sinne der Beendigungsklausel des Abkommens über die Rechtsstellung der Flüchtlinge vorliegen (vgl. <ref-law>; Art. 1C Ziffer 1 - 6 FK; UNHCR, Handbuch über Verfahren und Kriterien zur Feststellung der Flüchtlingseigenschaft, Genf 1979, Stand Dezember 2003, Rz. 111 ff.). Im Aufnahmestaat begangene Straftaten sind kein Aberkennungsgrund; der Betroffene bleibt - solange er materiell weiterhin als Flüchtling im Sinne von Art. 1 FK zu gelten hat - im Genuss des ihm konventionsrechtlich gewährten völkerrechtlichen Schutzes (EMARK 2003 Nr. 11). Das Bundesamt widerruft indessen - trotz der Flüchtlingseigenschaft - das Asyl, wenn der Betroffene die innere oder äussere Sicherheit der Schweiz verletzt, gefährdet oder besonders verwerfliche strafbare Handlungen begangen hat (<ref-law>; vgl. das Urteil des Bundesverwaltungsgerichts E-4830/2006 vom 30. August 2007, E. 4). Dem Flüchtling ohne Asyl muss unter Umständen im international-flüchtlingsrechtlichen Kontext ein subsidiärer, zum Asyl komplementärer Schutz (in der Schweiz in Form der vorläufigen Aufnahme) gewährt werden (vgl. Art. 83 Abs. 8 AuG; WALTER STÖCKLI, Asyl, in: Uebersax et al., Ausländerrecht, a.a.O., Rz. 11.48 u. 11.77 ff.; PETER BOLZLI, in: Spescha et al., Migrationsrecht, Zürich 2008, Vorbemerkungen zu Art. 83-88 sowie N. 26 zu Art. 83 AuG).
2.2.2 Kein Flüchtling darf in irgendeiner Form zur Ausreise in ein Land gezwungen werden, in dem sein Leib, sein Leben oder seine Freiheit wegen seiner Rasse, Religion, Nationalität, Zugehörigkeit zu einer bestimmten sozialen Gruppe oder wegen seiner politischen Anschauung gefährdet ist oder in dem er Gefahr läuft, zur Ausreise in ein solches Land gezwungen zu werden (<ref-law> bzw. Art. 33 Ziff. 1 FK). Dieser als Rückschiebeverbot bzw. Non-Refoulement-Gebot bezeichnete Grundsatz entfällt, wenn erhebliche Gründe für die Annahme bestehen, dass der Betroffene die Sicherheit der Schweiz gefährdet, oder wenn er als "gemeingefährlich" zu gelten hat, weil er wegen eines besonders schweren Verbrechens oder Vergehens rechtskräftig verurteilt worden ist (<ref-law> bzw. Art. 33 Ziff. 2 FK). Nur ein besonders schweres Verbrechen vermag den Rückschiebeschutz von <ref-law> aufzuheben. Eine Ausnahme vom Non-Refoulement-Prinzip rechtfertigt sich bloss, wenn der Täter für die Allgemeinheit des Zufluchtsstaats eine Gefahr bildet. Auf die entsprechende Gemeingefährlichkeit darf nicht allein aufgrund der Verurteilung wegen des besonders schweren Verbrechens geschlossen werden; es muss zusätzlich vielmehr eine konkrete Wiederholungsgefahr bestehen (Urteile 2A.139/1994 vom 1. Juli 1994 E. 6 mit Hinweisen auf die Doktrin, bestätigt im Urteil 2A.51/2006 vom 8. Mai 2006, E. 5.2). Keine solche Ausnahme kennt das Folterverbot (vgl. die Urteile des EGMR i.S. Ahmed gegen Österreich vom 17. Dezember 1996, Recueil CourEDH 1996-VI S. 2195, Ziff. 46; i.S. Chahal gegen Grossbritannien vom 15. November 1996, Recueil CourEDH 1996-V S. 1831, Ziff. 79 f., und i.S. Soering gegen Grossbritannien vom 7. Juli 1989, Serie A, Band 161, Ziff. 88 f.). Nach dem Völkerrecht sind Folter und jede andere Art grausamer, unmenschlicher oder erniedrigender Behandlung oder Bestrafung absolut verboten (Art. 3 EMRK, Art. 7 und Art. 10 Ziff. 1 UNO-Pakt II [SR 0.103.2]; KÄLIN/MALINVERNI/NOWAK, Die Schweiz und die UNO-Menschenrechtspakte, Basel 1997, S. 165 ff.). Niemand darf in einen Staat ausgeschafft werden, in dem ihm Folter oder eine andere Art grausamer und unmenschlicher Behandlung oder Bestrafung droht (<ref-law>; Art. 3 Ziff. 1 des Übereinkommens vom 10. Dezember 1984 gegen Folter und andere grausame, unmenschliche oder erniedrigende Behandlung oder Strafe [Folterschutzkonvention; SR 0.105]; Urteil 2A.313/2005 vom 25. August 2005 E. 2.2).
2.3 Ist der Vollzug der Weg- oder Ausweisung nicht zulässig, nicht zumutbar oder nicht möglich, so regelt das Bundesamt für Migration das Anwesenheitsverhältnis des betroffenen Ausländers oder Flüchtlings nach den Bestimmungen über die vorläufige Aufnahme (<ref-law> in Verbindung mit Art. 14a - 14c ANAG bzw. Art. 83 ff. AuG; ZÜND/ARQUINT HILL, in: Uebersax et al., Ausländerrecht, a.a.O., Rz. 8.98 ff.; WALTER STÖCKLI, in: Uebersax et al., Ausländerrecht, a.a.O., Rz. 11.65 ff.). Der Vollzug der Weg- oder Ausweisung ist nicht möglich, wenn die ausländische Person weder in den Heimat- oder in den Herkunftsstaat noch in einen Drittstaat ausreisen oder dorthin verbracht werden kann (Art. 14a Abs. 2 ANAG; Art. 83 Abs. 2 AuG). Der Vollzug ist unzulässig, wenn völkerrechtliche Verpflichtungen der Schweiz - wie etwa das flüchtlingsrechtliche Non-Refoulement-Gebot (Art. 33 FK) oder Art. 3 EMRK (vgl. <ref-ruling> E. 2a S. 235 ff.) -der Reise des Ausländers in seinen Heimat-, Herkunfts- oder einen Drittstaat entgegenstehen (Art. 14a Abs. 3 ANAG; Art. 83 Abs. 3 AuG). Nach Art. 14a Abs. 4 ANAG ist der Vollzug der Ausweisung unzumutbar, wenn er für den Betroffenen eine konkrete Gefährdung darstellt; er etwa im Heimat- oder Herkunftsstaat auf Grund von Situationen wie Krieg, Bürgerkrieg, allgemeiner Gewalt und medizinischer Notlage konkret gefährdet erscheint (vgl. Art. 83 Abs. 4 AuG). Die vorläufige Aufnahme ist trotz Unmöglichkeit oder Unzumutbarkeit der Ausweisung ausgeschlossen, "wenn der weg- oder ausgewiesene Ausländer die öffentliche Sicherheit und Ordnung verletzt hat oder diese in schwerwiegender Weise gefährdet" (Art. 14a Abs. 6 ANAG) bzw. die weg- oder ausgewiesene Person (a.) zu einer längerfristigen Freiheitsstrafe im In- oder Ausland verurteilt oder gegen sie eine strafrechtliche Massnahme im Sinne von Art. 64 oder 61 StGB angeordnet wurde; (b.) sie erheblich oder wiederholt gegen die öffentliche Sicherheit und Ordnung in der Schweiz oder im Ausland verstossen hat bzw. diese oder die innere oder die äussere Sicherheit gefährdet; oder (c.) sie die Unmöglichkeit des Vollzugs der Weg- oder Ausweisung durch ihr eigenes Verhalten verursacht hat (Art. 83 Abs. 7 AuG). Die Ausschlussgründe beziehen sich nur auf die vorläufige Aufnahme, die gestützt auf die Unzumutbarkeit oder die Unmöglichkeit des Weg- oder Ausweisungsvollzugs in Betracht fällt; sie sind unbeachtlich bei völkerrechtlichen Vollzugshindernissen (Unzulässigkeit); das Schutzbedürfnis der betroffenen Person überwiegt in diesem Fall die Sicherheitsinteressen und gilt deshalb absolut (PETER BOLZLI, in: Spescha et al., a.a.O., N. 21 und 24 zu Art. 83 AuG).
3. 3.1 Die asyl- und ausländerrechtliche Anwesenheitsregelung bzw. -beendigung eines anerkannten Flüchtlings sind miteinander verknüpft (vgl. dazu WALTER STÖCKLI, in: Uebersax et al., Ausländerrecht, a.a.O., Rz. 11.64; ZÜND/ARQUINT HILL, in: Uebersax et al., Ausländerrecht, a.a.O., Rz. 8.89 ff. und 8.101; NICOLAS WISARD, Les renvois et leur exécution en droit des étrangers et en droit d'asile, Basel/Frankfurt 1997, S. 464 ff.; MINH SON NGUYEN, Droit public des étrangers, Bern 2003, S. 625 ff.): Nach <ref-law> dürfen Flüchtlinge im ausländerrechtlichen Verfahren nur aus- oder weggewiesen werden, falls sie die innere oder äussere Sicherheit der Schweiz gefährden oder die öffentliche Ordnung in schwerwiegender Weise verletzt haben; nach <ref-law> widerruft das Bundesamt unter ähnlichen Voraussetzungen das Asyl; nach <ref-law> ist die asylrechtliche Beurteilung des Flüchtlingsstatus für alle eidgenössischen und kantonalen Behörden verbindlich, womit nicht zum Vornherein klar ist, welcher Beurteilungsraum den kantonalen Ausländerbehörden im Rahmen der Aufenthaltsregelung oder eines allfälligen Wegweisungsvollzugs eines anerkannten Flüchtlings verbleibt. Die Asylgewährung verschafft der betroffenen Person einen Anspruch darauf, dass ihr Aufenthalt ausländerrechtlich geregelt wird; sie erhält eine (Jahres-)Aufenthaltsbewilligung und nach fünf Jahren rechtmässigen Aufenthalts regelmässig die Niederlassung (<ref-law>). Damit geht das Asyl bei seiner Erteilung den ausländerrechtlichen Regeln über den Aufenthalt in der Schweiz vor; hingegen wird die einmal erteilte (ausländerrechtliche) Aufenthalts- oder Niederlassungsbewilligung durch den (nachträglichen) Widerruf des Asyls nicht (direkt) berührt. Die ausländerrechtliche Beendigung des Aufenthalts bedarf vielmehr (zusätzlich) eines eigenständigen Entscheids der kantonalen Behörden nach Massgabe der ausländerrechtlichen Widerrufs- oder Nichterneuerungsgründe (Art. 10 Abs. 1 lit. a ANAG i.V.m. <ref-law>; Urteil 2A.313/2005 vom 25. August 2005 E. 3.3.3 mit Hinweisen).
3.2 Nach der Rechtsprechung soll in der Regel über die ausländerrechtliche Aufenthaltsbeendigung und die damit verbundene Frage, ob deren Vollzug asyl- bzw. flüchtlingsrechtliche Gründe entgegenstehen, in einer einzigen, mit dem Bundesamt für Migration koordiniert zu erlassenden Verfügung entschieden werden (vgl. das Urteil 2A.51/2006 vom 8. Mai 2006 E. 2.3 mit Hinweisen). Nach <ref-law> erlischt das Asyl, wenn die Ausweisung vollzogen worden ist; dabei geht das Erlöschen des Asyls dessen Widerruf vor (Art. 43 Abs. 1 AsylV 1 [SR 142.311]). Die Regelung bezweckt, die formell-rechtliche Situation der tatsächlichen anzupassen und das Asyl ex lege dahinfallen zu lassen, wenn sich der betroffene Ausländer wegen der ausländerrechtlichen Aus- oder Wegweisung, in deren Rahmen die flüchtlingsrechtlichen Vollzugshindernisse spätestens im Vollstreckungsverfahren geprüft werden müssen, gar nicht mehr in der Schweiz aufhält (Urteil 2A.313/2005 vom 25. August 2005 E. 3.3). Die kantonale Behörde muss die Frage, ob die mit dem Verlust des ausländerrechtlichen Anwesenheitsrechts verbundene Wegweisung vermutlich auch wird vollzogen werden können, deshalb regelmässig in ihre umfassende Interessenabwägung miteinbeziehen; sie kann hierfür beim Bundesamt eine Stellungnahme zu allfälligen Vollzugshindernissen bzw. zum geplanten weiteren asyl- bzw. flüchtlingsrechtlichen Vorgehen einholen (Art. 43 Abs. 2 AsylV 1; Urteil 2A.313/2005 vom 25. August 2005 E. 3.3.3). Kommt sie oder ihre Rechtsmittelinstanz zum Schluss, dass das Rückschiebeverbot, Art. 3 EMRK oder das Folterverbot dem Vollzug der Ausweisung entgegenstehen, fällt der Asyl- bzw. materielle Flüchtlingsstatus (ohne dessen Widerruf) nicht automatisch dahin (vgl. <ref-law>), da die Ausweisung nicht vollzogen wurde bzw. werden kann; die kantonale Migrationsbehörde muss in diesem Fall das Bundesamt gestützt auf Art. 14a ff. ANAG bzw. auf Art. 83 AuG darum ersuchen, den Status des Betroffenen flüchtlingsrechtlich neu zu bestimmen (Urteil 2A.313/2005 vom 25. August 2005 E. 3.3.3; bestätigt im Urteil 2A.51/2006 vom 8 Mai 2006 E. 2.3). Eine Aufteilung auf zwei ausländerrechtliche Verfahren (Ausweisung einerseits und kantonaler Vollzugsentscheid andererseits) - analog der früheren Praxis bei der strafrechtlichen Landesverweisung - erweist sich vor diesem Hintergrund als wenig zweckmässig (vgl. das Urteil 2A.313/2005 vom 25. August 2005 E. 3.3.2), ist indessen nicht bundesrechtswidrig, falls dabei sichergestellt bleibt, dass sämtliche Fragen in einem rechtsstaatlich korrekten Verfahren umfassend geprüft werden und die nach Art. 11 ANAG in Verbindung mit Art. 16 ANAV für die Ausweisung gebotene Interessenabwägung keine unzulässige Beschränkung erfährt (vgl. die Urteile 2A.313/2005 vom 25. August 2005 E. 3.3 und 2C_87/2007 vom 18. Juni 2007 E. 2).
4. 4.1 Der Beschwerdeführer ist unbestrittenermassen in der Schweiz im Sinne von Art. 10 Abs. 1 lit. a ANAG straffällig geworden. Die Schwere seines Verschuldens darf dabei nicht unterschätzt werden: Zwar ist er vom Vorwurf der versuchten vorsätzlichen Tötung freigesprochen worden, doch verurteilte ihn das Geschworenengericht des Kantons Zürich am 28. Januar 2004 wegen Gefährdung des Lebens, wegen mehrfacher untauglich versuchter Gefährdung des Lebens und wegen mehrfachen Vergehens gegen das Waffengesetz zu 4 1⁄2 Jahren Zuchthaus, nachdem er am 26. September 2001 in einem gut besetzten Restaurant mehrere Schüsse in die Decke, in eine Glasvitrine und von aussen auf eine Fensterscheibe, hinter der zwei Gäste sassen, abgegeben hatte. Der Beschwerdeführer habe, nachdem ihm kein Bier ausgeschenkt und er kritisiert worden sei, die Sicht auf den Karaoke-Monitor zu versperren, für die Wiederherstellung seines verloren geglaubten Gesichts bzw. zum Verschaffen des "nötigen" Respekts skrupellos die Gefährdung unbeteiligter Dritter in Kauf genommen. Die Taten seien aus "absolut nichtigem Anlass" erfolgt, weshalb sein Verschulden objektiv wie subjektiv schwer wiege, was denn auch in der Strafhöhe von 4 1⁄2 Jahren Zuchthaus zum Ausdruck kam. Ins Gewicht fällt zudem, dass der Beschwerdeführer bereits am 9. Oktober 1997 wegen einfacher Körperverletzung und Sachbeschädigung zu einer Busse von Fr. 400.-- und am 9. Mai 2001 wegen Betrugs und Diebstahls zu einer Gefängnisstrafe von 3 Monaten (bedingt auf drei Jahre) verurteilt worden war, womit seine Straftaten in Zürich in die entsprechende Probezeit fielen. Der Beschwerdeführer hat damit massiv gegen die hiesigen strafrechtlichen und moralischen Normen verstossen und die öffentliche Ordnung in schwerwiegender Weise im Sinne von <ref-law> gestört, weshalb sein Asyl (rechtskräftig) widerrufen wurde.
4.2 Eine Ausweisung rechtfertigt sich - wie dargelegt (vgl. oben E. 2.1) - indessen nur, wenn sie sich gestützt auf die gesamten wesentlichen Umstände auch als verhältnismässig erweist. Entgegen der Annahme des Rekursgerichts können bei der entsprechenden Beurteilung jene Aspekte nicht ausser Acht gelassen werden, die sich daraus ergeben, dass "die Rückkehr in den Heimatstaat aufgrund der aktuellen Situation im Heimatland" (vorerst) allenfalls "unzumutbar" erscheint (E. 2.3 des angefochtenen Entscheids): Ob der Vollzug der Weg- oder Ausweisung eines Flüchtlings zulässig, zumutbar oder möglich ist, beurteilt das Bundesamt bzw. das Bundesverwaltungsgericht im Rahmen des Entscheids über die vorläufige Aufnahme als Ersatzmassnahme für die Wegweisung (vgl. oben E. 2.3). Die ausländerrechtliche Interessenabwägung bei der Ausweisung oder dem Bewilligungswiderruf muss ihrerseits jedoch bereits sämtliche wesentlichen Aspekte erfassen, wozu auch die Zumutbarkeit der Rückkehr ins Heimatland im bewilligungsrechtlichen Gesamtzusammenhang gehört; die ausländerrechtliche Weg- oder Ausweisungsverfügung kann beim Entscheid über die vorläufige Aufnahme als solche nicht mehr in Frage gestellt werden. In das Vollstreckungsverfahren dürfen deshalb nur Aspekte, welche die Unzulässigkeit, nicht aber solche, welche die Unzumutbarkeit des Wegweisungsvollzugs betreffen, verschoben werden, da nur jene dort auf jeden Fall geprüft werden müssen. Die vorläufige Aufnahme als wegweisungsrechtliche Ersatzmassnahme kann jederzeit aufgehoben werden, falls der Wegweisungsvollzug wieder zulässig, möglich oder zumutbar erscheint, weshalb die entsprechenden Umstände bei der ausländerrechtlichen Beendigung des Anwesenheitsrechts und der hierfür erforderlichen Interessenabwägung nicht übergangen werden dürfen. Dem Bundesamt bzw. dem Bundesverwaltungsgericht steht es frei, das kantonale Gesuch, die weg- oder ausgewiesene Person vorläufig aufzunehmen, abzuweisen, was gemäss jüngeren Urteilen für Kambodscha bei ähnlichen Verhältnissen wie hier inzwischen regelmässig der Fall zu sein scheint (vgl. die Urteile des Bundesverwaltungsgerichts 2C-2019/2007 und 2C-2642/2007 vom 18. und 19. Dezember 2007). In solchen Fällen wird die Zumutbarkeit des Wegweisungsvollzugs bei der vorläufigen Aufnahme gestützt auf Art. 14 Abs. 6 ANAG bzw. Art. 83 Abs. 7 AuG nicht mehr geprüft, weshalb sie (zumindest) Gegenstand des ausländerrechtlichen Verfahrens bilden muss, andernfalls sie unberücksichtigt bleibt. Die Zumutbarkeit der Rückkehr bzw. des Vollzugs der Wegweisung bildet somit - was das Rekursgericht verkannt hat - Teil der umfassenden Interessenabwägung nach Art. 11 ANAG bzw. Art. 16 ANAV.
4.2 Eine Ausweisung rechtfertigt sich - wie dargelegt (vgl. oben E. 2.1) - indessen nur, wenn sie sich gestützt auf die gesamten wesentlichen Umstände auch als verhältnismässig erweist. Entgegen der Annahme des Rekursgerichts können bei der entsprechenden Beurteilung jene Aspekte nicht ausser Acht gelassen werden, die sich daraus ergeben, dass "die Rückkehr in den Heimatstaat aufgrund der aktuellen Situation im Heimatland" (vorerst) allenfalls "unzumutbar" erscheint (E. 2.3 des angefochtenen Entscheids): Ob der Vollzug der Weg- oder Ausweisung eines Flüchtlings zulässig, zumutbar oder möglich ist, beurteilt das Bundesamt bzw. das Bundesverwaltungsgericht im Rahmen des Entscheids über die vorläufige Aufnahme als Ersatzmassnahme für die Wegweisung (vgl. oben E. 2.3). Die ausländerrechtliche Interessenabwägung bei der Ausweisung oder dem Bewilligungswiderruf muss ihrerseits jedoch bereits sämtliche wesentlichen Aspekte erfassen, wozu auch die Zumutbarkeit der Rückkehr ins Heimatland im bewilligungsrechtlichen Gesamtzusammenhang gehört; die ausländerrechtliche Weg- oder Ausweisungsverfügung kann beim Entscheid über die vorläufige Aufnahme als solche nicht mehr in Frage gestellt werden. In das Vollstreckungsverfahren dürfen deshalb nur Aspekte, welche die Unzulässigkeit, nicht aber solche, welche die Unzumutbarkeit des Wegweisungsvollzugs betreffen, verschoben werden, da nur jene dort auf jeden Fall geprüft werden müssen. Die vorläufige Aufnahme als wegweisungsrechtliche Ersatzmassnahme kann jederzeit aufgehoben werden, falls der Wegweisungsvollzug wieder zulässig, möglich oder zumutbar erscheint, weshalb die entsprechenden Umstände bei der ausländerrechtlichen Beendigung des Anwesenheitsrechts und der hierfür erforderlichen Interessenabwägung nicht übergangen werden dürfen. Dem Bundesamt bzw. dem Bundesverwaltungsgericht steht es frei, das kantonale Gesuch, die weg- oder ausgewiesene Person vorläufig aufzunehmen, abzuweisen, was gemäss jüngeren Urteilen für Kambodscha bei ähnlichen Verhältnissen wie hier inzwischen regelmässig der Fall zu sein scheint (vgl. die Urteile des Bundesverwaltungsgerichts 2C-2019/2007 und 2C-2642/2007 vom 18. und 19. Dezember 2007). In solchen Fällen wird die Zumutbarkeit des Wegweisungsvollzugs bei der vorläufigen Aufnahme gestützt auf Art. 14 Abs. 6 ANAG bzw. Art. 83 Abs. 7 AuG nicht mehr geprüft, weshalb sie (zumindest) Gegenstand des ausländerrechtlichen Verfahrens bilden muss, andernfalls sie unberücksichtigt bleibt. Die Zumutbarkeit der Rückkehr bzw. des Vollzugs der Wegweisung bildet somit - was das Rekursgericht verkannt hat - Teil der umfassenden Interessenabwägung nach Art. 11 ANAG bzw. Art. 16 ANAV.
4.3 4.3.1 Bei einer in diesem Sinn verstandenen umfassenden Berücksichtigung aller wesentlichen Umstände überzeugt die Interessenabwägung des Rekursgerichts nicht. Zwar ist der Beschwerdeführer - wie dargelegt - in nicht zu verharmlosender Weise straffällig geworden, seine Ausweisung erscheint jedoch gestützt auf die gesamten Umstände (einschliesslich der Zumutbarkeit einer Rückkehr in seine Heimat) unverhältnismässig: Der Beschwerdeführer ist 1979 über südostasiatische Flüchtlingslager als knapp 22-jähriger kambodschanischer Flüchtling chinesischer Abstammung in die Schweiz gekommen, wo er Asyl erhielt. Er lebt heute somit seit rund 30 Jahren im Land. Auch wenn seine Ehe inzwischen auseinandergegangen ist, hat er mit seiner Frau die gemeinsamen Kinder hier grossgezogen. In seiner Heimat verfügt er - unbestrittenermassen - über keinerlei Familienangehörige mehr; er hat auch keine persönlichen oder wirtschaftlichen Kontakte mehr zu seinem Heimatstaat. Das Geschworenengericht unterstrich im Strafurteil, dass der Beschwerdeführer seit seiner Ankunft in der Schweiz fast durchwegs erwerbstätig gewesen und seinem Lebensunterhalt auf ehrliche Weise nachgekommen sei. Seine schlimmen Erlebnisse während der Kindheit und Jugend in Kambodscha sowie der Umstand, dass er seit seinem 17. oder 18. Altersjahr keinen Kontakt zu seinen Eltern bzw. Geschwistern und keine Kenntnis über deren Schicksal mehr habe, stelle für ihn "eine schwere seelische Hypothek" dar; es sei deshalb "denkbar", dass diese Vorgeschichte "in Form einer daraus resultierenden überdurchschnittlichen Reizbarkeit" für die zu beurteilenden Delikte von einer gewissen Bedeutung gewesen seien, was strafmildernd berücksichtigt werden könne.
4.3.2 Zwar ist das Interesse, einen straffällig gewordenen Ausländer von der Schweiz fernzuhalten, in erster Linie aufgrund seines bisherigen Verhaltens und seines strafrechtlichen Verschuldens zu beurteilen; dies bedeutet indessen nicht, dass die im Strafverfahren erfolgte Einschätzung der Rückfallgefahr dabei überhaupt keine Rolle spielen würde, zumal die kantonalen Behörden vorliegend (selber) davon ausgehen, dass der Betroffene das Land nicht wird verlassen, sondern hier als anerkannter Flüchtling vorläufig aufgenommen werden müssen. Durch die Ausweisung wird bei dieser Ausgangslage somit lediglich sein Aufenthaltsstatus (hinsichtlich der Arbeitsmöglichkeiten, Sozialfürsorge usw. in untergeordneter Weise) verändert. Eine Ausweisung bzw. ein Widerruf der Niederlassungsbewilligung trotz anerkanntem Flüchtlingsstatus rechtfertigt sich - mit Blick auf dessen Integrationszweck (vgl. UNHCR, Handbuch über Verfahren und Kriterien zur Feststellung der Flüchtlingseigenschaft, a.a.O., Rz. 111 ff.) - unter diesen Umständen nur, wenn tatsächlich eine minimal konkretisierte und nicht lediglich eine rein abstrakte Wiederholungsgefahr besteht.
4.3.3 Eine solche ist hier nicht dargetan: Der psychiatrische Sachverständige kam im Strafverfahren zum Schluss, dass die Wahrscheinlichkeit einer neuerlichen vergleichbaren Tathandlung aus forensisch-psychiatrischer Sicht als "eher gering" einzuschätzen sei, was das Geschworenengericht zur Feststellung veranlasste, dass das Schutzbedürfnis der Schweiz untergeordnet und auf "die Aussprechung einer Landesverweisung" daher "klarerweise" zu verzichten sei. Auch das Migrationsamt des Kantons Aargau hielt in seiner Ausweisungsverfügung fest, dass der Beschwerdeführer konkret weder die Sicherheit der Schweiz gefährde, noch als gemeingefährlich zu gelten habe; mit Verfügung vom 4. April 2004 sei er vom Strafvollzugsdienst des Kantons Zürich auf den 22. April 2005 bedingt aus dem Strafvollzug entlassen worden, wobei seither nichts aktenkundig sei, "wonach der Betroffene wieder straffällig geworden" wäre oder eine "konkrete Wiederholungsgefahr" bestehen könnte. Das Rekursgericht hat diese Einschätzung nicht bestritten, sondern lediglich erklärt, dass das öffentliche Interesse als "noch höher" zu veranschlagen wäre, "wenn eine konkrete gegenwärtige Gefährdung konstatiert werden müsste" (E. 4.2.2). Da es damit gerade keine solche festgestellt hat, der Beschwerdeführer bis auf seine Straffälligkeit bisher hier gesellschaftlich und beruflich integriert war, seine Resozialisierungschancen in der Schweiz klar besser sind als in Kambodscha und seit dem Ende des Strafvollzugs schliesslich nichts Nachteiliges mehr über ihn bekannt geworden ist, erweist sich seine Ausweisung als unverhältnismässig. Muss der Beschwerdeführer als anerkannter Flüchtling gelten (vgl. <ref-law>) und soll er nach der Ansicht der kantonalen Ausländerbehörden als vorläufig Aufgenommener so oder anders in der Schweiz verbleiben können, rechtfertigt sich seine Ausweisung, die lediglich die Niederlassungsbewilligung dahinfallen, aber sein Anwesenheitsrecht unberührt lässt, nicht; die Ausweisung ist in diesem Fall von Vornherein nicht geeignet, durch die Fernhaltung des Betroffenen die Sicherheit in der Schweiz zu erhöhen, falls tatsächlich ein relevantes Rückfallrisiko fortbestehen sollte.
4.3.4 Die vom Bundesgericht anders beurteilten Fälle, auf die sich das Rekursgericht bezieht, können mit dem vorliegenden Sachverhalt nicht verglichen werden: Dem Urteil 2A.51/2006 vom 8. Mai 2006 (türkischer Flüchtling, vier Jahre Zuchthaus unter anderem wegen bandenmässigen Raubs, Aufenthalt bis zur Ausweisung von rund acht Jahren, fehlende berufliche und soziale Integration) lag ein psychiatrisches Gutachten zugrunde, welches dem Betroffenen eine emotional instabile Persönlichkeit vom Typ Borderline bescheinigte und festhielt, dass er dementsprechend unbeherrscht und impulsiv wirke; er neige wohl dazu, "kurzschlüssig zu reagieren"; gestützt hierauf lasse er "eine nicht unbeträchtliche Gefährlichkeit für Dritte erkennen". In den Entscheiden 2C_87/2007 bzw. 2A.51/2006 vom 18. Juni 2007 bzw. 8. Mai 2006 (türkischer Flüchtling, 5 1⁄2 Jahre Zuchthaus unter anderem wegen mehrfacher versuchter Tötung [Grenzfall zu Mord] und mehrfacher Gefährdung des Lebens, Aufenthalt bis zur Ausweisung von vierzehn Jahren, fehlende berufliche und soziale Integration) war aufgrund der Akten eine relevante Rückfallgefahr ebenfalls nicht auszuschliessen: Das Bundesgericht hielt aufgrund der Gutachten und des Urteils seines Kassationshofs fest, dass beim Beschwerdeführer - da eine hinreichende Aufarbeitung des familiären Konflikts, der die Ursache der Tat gebildet habe, bislang unterblieben sei - nach wie vor eine Rückfallgefahr bestehe, welche die Ausweisung rechtfertige, selbst wenn die Resozialisierungschancen in der Schweiz besser sein sollten als in der Heimat (Urteil 2A.51/2006 E. 3.2.2). Der Gutachter war seinerseits zum Schluss gekommen, dass beim Beschwerdeführer angesichts seiner bescheidenen Problemverarbeitungsmöglichkeiten weitere aggressive Handlungen gegen die Familie nicht ausgeschlossen werden könnten; es bestehe deshalb eine "erhebliche Rückfallgefahr im innerfamiliären Bereich" (Urteil 2A.51/2006 E. 3.1.1.; vgl. auch das Urteil 2C_87/2007 E. 4.2.3).
5. 5.1 Die Beschwerde ist somit gutzuheissen und der angefochtene Entscheid aufzuheben. Das Rekursgericht wird über die Kosten- und Entschädigungsfrage für die kantonalen Verfahren neu zu befinden haben (vgl. <ref-law>).
5.2 Dem Verfahrensausgang entsprechend sind für das bundesgerichtliche Verfahren keine Kosten geschuldet (vgl. <ref-law>). Der Kanton Aargau hat den Beschwerdeführer für dieses jedoch angemessen zu entschädigen (<ref-law>). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird dadurch gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und das Urteil des Rekursgerichts im Ausländerrecht des Kantons Aargau vom 22. August 2008 wird aufgehoben.
2. Es werden keine Kosten erhoben.
3. Der Kanton Aargau hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
5. Dieses Urteil wird den Parteien, dem Rekursgericht im Ausländerrecht des Kantons Aargau und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 16. Februar 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Hugi Yar