Sachverhalt:
A. X._ (geb. 1976) stammt aus der Türkei. Das Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) gewährte ihm am 16. Januar 2001 Asyl, das es am 16. Februar 2007 widerrief, nachdem das Geschworenengericht des Kantons Zürich X._ wegen versuchter vorsätzlicher Tötung zu 7 1⁄2 Jahren Zuchthaus verurteilt hatte. Am 4. November 2008 lehnte das Migrationsamt des Kantons Zürich es ab, die Aufenthaltsbewilligung von X._ zu verlängern, wogegen dieser an den Regierungsrat des Kantons Zürich gelangte. Mit Verfügung vom 17. November 2008 entschied die Staatskanzlei, dass vom Vollzug der damit verbundenen Wegweisung vorläufig abzusehen sei.
B. Mit Verfügung vom 26. November 2008 nahm das Migrationsamt des Kantons Zürich X._ in Ausschaffungshaft, welche die Haftrichterin am Bezirksgericht Zürich am 28. November 2008 prüfte und bis zum 24. Februar 2009 bestätigte. Das Gesuch von X._, seinen Rechtsvertreter als unentgeltlichen Rechtsbeistand zu ernennen, wies sie mit der Begründung ab, dass sich weder in tatsächlicher noch in rechtlicher Hinsicht komplexe Fragen stellten.
C. X._ ist am 29. Dezember 2008 mit dem Antrag an das Bundesgericht gelangt, den haftrichterlichen Entscheid insoweit aufzuheben, als darin sein Gesuch um Bestellung eines unentgeltlichen Rechtsbeistands abgewiesen wurde (Ziffer 1 des Dispositivs); allenfalls sei die Sache zu neuem Entscheid hierüber an die Vorinstanz zurückzuweisen. Das Bezirksgericht Zürich und das Bundesamt für Migration haben darauf verzichtet, sich vernehmen zu lassen.

Erwägungen:
1. Gegen kantonal letztinstanzliche Entscheide über Zwangsmassnahmen im Ausländerrecht und damit verbundene Verfügungen betreffend die Verbeiständung ist die öffentlich-rechtliche Beschwerde an das Bundesgericht zulässig. Nach <ref-law> setzen die Kantone als unmittelbare Vorinstanzen des Bundesgerichts obere Gerichte ein, soweit nicht nach einem anderen Bundesgesetz Entscheide richterlicher Behörden direkt der Beschwerde an das Bundesgericht unterliegen. Die entsprechende Anpassungsfrist ist am 1. Januar 2009 abgelaufen (vgl. <ref-law>). Da der angefochtene Entscheid indessen noch vor diesem Zeitpunkt erging, ist auf die frist- und formgerecht eingereichte Beschwerde gegen die Verfügung des Bezirksgerichts einzutreten (Urteil 2C_35/2009 vom 13. Februar 2009 E. 1; vgl. auch BGE 2C_10/2009 vom 5. Februar 2009 E. 3 - 5).
2. 2.1 Gegenstand des vorliegenden Verfahrens bildet ausschliesslich die Frage, ob die Vorinstanz das Gesuch um unentgeltliche Verbeiständung zu Recht abgewiesen hat; die Haftgenehmigung als solche ist nicht angefochten. Der Beschwerdeführer rügt keine Verletzung kantonaler Verfahrensbestimmungen, sondern macht ausschliesslich geltend, sein bundesverfassungsrechtlich gewährleisteter Anspruch auf Verbeiständung (<ref-law>) sei verletzt worden. Die Frage ist mit freier Kognition zu prüfen (<ref-ruling> E. 2.1 mit Hinweis).
2. 2.1 Gegenstand des vorliegenden Verfahrens bildet ausschliesslich die Frage, ob die Vorinstanz das Gesuch um unentgeltliche Verbeiständung zu Recht abgewiesen hat; die Haftgenehmigung als solche ist nicht angefochten. Der Beschwerdeführer rügt keine Verletzung kantonaler Verfahrensbestimmungen, sondern macht ausschliesslich geltend, sein bundesverfassungsrechtlich gewährleisteter Anspruch auf Verbeiständung (<ref-law>) sei verletzt worden. Die Frage ist mit freier Kognition zu prüfen (<ref-ruling> E. 2.1 mit Hinweis).
2.2 2.2.1 Nach <ref-law> hat die bedürftige Partei einen Anspruch darauf, dass ihr ein unentgeltlicher Rechtsbeistand bestellt wird, soweit dies zur Wahrung ihrer Rechte notwendig ist und ihr Rechtsbegehren nicht aussichtslos erscheint. Unter diesen Voraussetzungen besteht ein Anspruch auf amtliche Vertretung. Daraus lässt sich indessen kein Recht auf eine obligatorische (notwendige) Verbeiständung ableiten; eine solche kann sich allenfalls aus anderen Verfassungsbestimmungen ergeben (<ref-ruling> E. 3.1 und E. 4). Im Unterschied zur amtlichen Verbeiständung, auf die ein verfassungsrechtlicher Anspruch nur besteht, wenn das gestellte Begehren nicht aussichtslos erscheint, darf die Beigabe eines unentgeltlichen Rechtsvertreters im Bereich der notwendigen Vertretung nicht davon abhängig gemacht werden, dass die Erfolgsaussichten die Verlustgefahren überwiegen; dieser Anspruch findet seine Schranken allein im Rechtsmissbrauchsverbot (<ref-ruling> E. 4.5).
2.2.2 Im Bereich der ausländerrechtlichen Administrativhaft hat das Bundesgericht erkannt, dass im Haftverlängerungsverfahren einem bedürftigen Häftling nach drei Monaten auf dessen Gesuch hin der unentgeltliche Rechtsbeistand in der Regel - unabhängig von den Erfolgsaussichten seiner Begehren - nicht verweigert werden darf (<ref-ruling> E. 2c/cc). Nach <ref-law> muss jede Person, welcher die Freiheit entzogen wird, die Möglichkeit haben, ihre Rechte in einer den Umständen angemessenen, wirksamen Weise geltend zu machen, weshalb das Erfordernis der fehlenden Aussichtslosigkeit bei einem Freiheitsentzug von einer gewissen Intensität bzw. Dauer sachgerecht zu relativieren und differenziert zu handhaben ist (<ref-ruling> E. 3.2.3). In der Regel droht dem Ausländer bei der Haftverlängerung nach drei Monaten eine schwere Freiheitsbeschränkung, die für ihn mit rechtlichen und tatsächlichen Schwierigkeiten verbunden ist, denen er auf sich selber gestellt selbst in "einfachen" Fällen ohne anwaltliche Hilfe kaum (mehr) gewachsen erscheint (<ref-ruling> E. 3.2.3). Bei der erstmaligen Haftprüfung ist eine unentgeltliche Verbeiständung demgegenüber nicht vorbehaltlos geboten, sondern nur, wenn besondere Schwierigkeiten rechtlicher oder tatsächlicher Natur bestehen, welche eine solche (ausnahmsweise) rechtfertigen, was jeweils aufgrund der Umstände im Einzelfall zu prüfen ist (<ref-ruling> E. 3.2.2; <ref-ruling> E. 3b).
2.2.3 Entgegen den hierzu bloss summarischen Ausführungen im angefochtenen Entscheid bestanden vorliegend Schwierigkeiten, welche den Beizug eines Anwalts bereits bei der erstmaligen Haftgenehmigung rechtfertigten: Der Beschwerdeführer befindet sich seit dem 19. März 2003 in Haft; am 16. Februar 2007 wurde ihm das Asyl entzogen, doch blieb seine Flüchtlingseigenschaft erhalten. In solchen Fällen besteht ein komplexes Verhältnis zwischen den asyl- und ausländerrechtlichen Verfahren bzw. Zuständigkeiten (vgl. BGE 2C_710/ 2008 vom 16. Februar 2009 E. 2 und 3), die vom Betroffenen nicht ohne anwaltliche Beratung verstanden und im Haftprüfungsverfahren sachgerecht geltend gemacht werden können. Zwar bildet der Wegweisungsentscheid selber nicht Gegenstand der Haftprüfung (vgl. <ref-ruling> E. 2.2) und sind die damit verbundenen Fragen in erster Linie in den - hier inzwischen eingeleiteten - asyl- oder ausländerrechtlichen Verfahren zu prüfen, doch beeinflusst deren Komplexität die Problematik der Absehbarkeit des Wegweisungsvollzugs (Art. 80 Abs. 6 lit. a AuG) und damit verbunden die Verhältnismässigkeit bzw. Konventionskonformität der Zwangsmassnahme (vgl. <ref-ruling> ff.). Es ist nicht ausgeschlossen, dass der Wegweisungsvollzug in einer solchen Situation nicht mehr als schwebend im Sinne von Art. 5 lit. f EMRK gelten kann, womit eine Haft zu dessen Sicherung nicht mehr konventionskonform erschiene (vgl. <ref-ruling> ff.). Auch ist es im Hinblick auf das Beschleunigungsgebot (vgl. Art. 76 Abs. 4 AuG) nicht unproblematisch, wenn zwischen dem Asylwiderruf und dem ausländerrechtlichen Wegweisungsentscheid ohne sachlichen Grund ein Zeitraum liegt, welcher es erschwert, allfällige mit dem Vollzug der Wegweisung verbundene Rechtsmittelverfahren noch während des Strafvollzugs einleiten zu können, was die anschliessende Ausschaffungshaft verkürzen würde (vgl. HUGI YAR, Zwangsmassnahmen im Ausländerrecht, in: Uebersax et al. [Hrsg.], Ausländerrecht, 2. Aufl., 2009, Rz. 10.99 ff., insbesondere 10.101). Schliesslich hat sich das Bundesgericht, soweit ersichtlich, im Zusammenhang mit den Zwangsmassnahmen noch nie mit einer Problematik der vorliegenden Art befassen müssen. Der Fall bot damit Schwierigkeiten in tatsächlicher und rechtlicher Hinsicht, welche es nötig machten, dem Gesuch des Beschwerdeführers um die Beigabe seines Vertreters als Rechtsbeistand zu entsprechen. Es war ihm als Laien nicht möglich, ohne rechtskundigen Vertreter seine Interessen im Haftprüfungsverfahren wirksam geltend zu machen und in den Genuss eines (mit dem Migrationsamt) waffengleichen, fairen Verfahrens zu gelangen (vgl. Art. 5 Ziff. 4 EMRK; <ref-ruling> E. 3.2.4 mit Hinweisen).
3. 3.1 Die Beschwerde ist demnach gutzuheissen, die Ziffer 1 des Dispositivs des Entscheids des Bezirksgerichts Zürich vom 28. November 2008 aufzuheben und die Sache zu neuem Entscheid (Bestellung des Beistands und Festsetzung der Entschädigung) an die Vorinstanz zurückzuweisen.
3.2 Dem Verfahrensausgang entsprechend sind keine Kosten zu erheben (vgl. <ref-law>; HANSJÖRG SEILER, Bundesgerichtsgesetz [BGG], 2007, Rz. 52 zu <ref-law>). Der Kanton Zürich muss den anwaltlich vertretenen Beschwerdeführer für dessen Aufwand jedoch angemessen entschädigen (vgl. <ref-law>). Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, Ziffer 1 des Dispositivs des Entscheids des Bezirksgerichts Zürich vom 28. November 2008 wird aufgehoben und die Sache wird zu neuem Entscheid über die Verbeiständung an die Vorinstanz zurückgewiesen.
2. 2.1 Es werden keine Kosten erhoben.
2.2 Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
2.3 Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
3. Dieses Urteil wird den Parteien, dem Bezirksgericht Zürich, Haftrichterin, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 28. April 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Hugi Yar