Sachverhalt:
A. X._ (geb. 1950) stammt aus der Türkei. Er reiste am 9. Juni 1988 in die Schweiz ein, wurde als Flüchtling anerkannt und erhielt Asyl. Am 20. Februar 1995 wurde ihm die Niederlassungsbewilligung erteilt. Bereits im Juni bzw. Oktober 1994 war zweien seiner Söhne die Flüchtlingseigenschaft zuerkannt und Asyl gewährt worden. 1995 reisten seine Ehefrau und weitere gemeinsame Kinder in die Schweiz ein, wo sie ebenfalls Asyl erhielten.
Anlässlich eines Streits im Herbst 2001 tötete X._ seine Ehefrau mit drei Kopfschüssen und einem Bauchschuss. Das Zürcher Obergericht befand ihn der vorsätzlichen Tötung für schuldig und bestrafte ihn mit acht Jahren Zuchthaus. Gleichzeitig ordnete es - aufgrund einer psychischen Erkrankung, die den schizophrenen Krankheitsbildern zuzurechnen ist - eine stationäre Massnahme gegen ihn an, aus der er am 28. April 2010 bedingt entlassen wurde. Seither erfolgte die psychiatrische Betreuung im Wohn- und Pflegeheim A._ wobei X._ schwere Rückfälle erlitt und erneut stationär psychiatrisch behandelt werden musste. Am 3. März 2009 widerrief das Bundesamt für Migration sein Asyl, beliess ihm aber den Flüchtlingsstatus.
B. Aufgrund seiner schweren Straffälligkeit widerrief die Sicherheitsdirektion des Kantons Zürich (Migrationsamt) am 28. Juni 2010 die Niederlassungsbewilligung von X._ und wies ihn aus der Schweiz weg. Den hiergegen erhobenen Rekurs lehnte der Regierungsrat des Kantons Zürich am 16. März 2011 ab. Eine dagegen gerichtete Beschwerde wies das Verwaltungsgericht des Kantons Zürich ab, soweit es darauf eintrat.
C. Vor Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts sei aufzuheben und es sei festzustellen, dass der Vollzug der Wegweisung gegen Art. 25 Abs. 2 und 3 BV, gegen Art. 3 der Genfer Flüchtlingskonvention (Abkommen über die Rechtsstellung der Flüchtlinge vom 28. Juli 1951, FK; SR 0.142.30), 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) sowie gegen Art. 3 und Art. 6 Ziff. 1 EMRK verstosse. Eventuell sei der Kanton Zürich anzuhalten, dem Bundesamt für Migration die vorläufige Aufnahme des Beschwerdeführers zu beantragen resp. bei einem neuen Entscheid seien zusätzliche Abklärungen des Sachverhalts vorzunehmen. X._ ersucht zudem um unentgeltliche Rechtspflege und Verbeiständung.
Das Verwaltungsgericht, der Regierungsrat des Kantons Zürich und das Bundesamt für Migration beantragen, die Beschwerde abzuweisen. Das Amt für Justizvollzug des Kantons Zürich resp. der dort Fallverantwortliche spricht sich sinngemäss für eine Gutheissung der Beschwerde aus, wurde allerdings nicht zur Vernehmlassung eingeladen.
D. Mit Verfügung vom 25. Januar 2012 hat der Abteilungspräsident der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist gegen Entscheide auf dem Gebiet des Ausländerrechts unzulässig, die Bewilligungen betreffen, auf die weder das Bundes- noch das Völkerrecht einen Anspruch einräumt (<ref-law>). Sie ist ausgeschlossen gegen Entscheide über die vorläufige Aufnahme (Ziff. 3) und die Wegweisung (Ziff. 4). Der Ausschlussgrund gilt nach dem Grundsatz der Einheit des Verfahrens (<ref-ruling> E. 1.3 S. 195; <ref-ruling> E. 3 S. 144; <ref-ruling> E. 2.2 S. 647 f.) auch, wenn damit diese Gebiete betreffende Vollzugsentscheide angefochten werden. Gegen entsprechende kantonale Entscheide steht indessen die subsidiäre Verfassungsbeschwerde offen (<ref-law>; Art. 114 i.V.m. <ref-law>; <ref-ruling> E. 1.1 S. 307; Urteil 2D_67/2009 vom 4. Februar 2010 E. 2.1). Der Betroffene kann in diesem Rahmen - in dem es nicht mehr um den negativen Sach-, sondern mit der Wegweisung lediglich noch um den damit verbundenen Vollzugsentscheid geht - keine Rügen erheben, die Gegenstand des Entscheids über den Widerruf bzw. über die Nichtverlängerung der Bewilligung gebildet haben oder hätten bilden müssen (<ref-ruling> E. 1.1 S. 307; Urteile 2C_425/2010 vom 17. August 2010 E. 4 und 2D_67/2009 vom 4. Februar 2010 E. 2.4 und 5). Das Migrationsamt des Kantons Zürich hat den Beschwerdeführer, welcher nach wie vor als Flüchtling im Sinne der Genfer Flüchtlingskonvention gilt, am 4. März 2010 angehalten, die Schweiz zu verlassen und das Vorliegen von Vollzugshindernissen verneint. Nur noch die Verfassungsmässigkeit des - durch das Verwaltungsgericht des Kantons Zürich am 30. November 2011 bestätigten - Vollzugs dieses Wegweisungsentscheids bildet Gegenstand der subsidiären Verfassungsbeschwerde, auf die in diesem Umfang grundsätzlich einzutreten ist (vgl. die weiteren Einschränkungen in E.1.2-1.4).
1.2 Zur Verfassungsbeschwerde ist legitimiert, wer (a) vor der Vorinstanz am Verfahren teilgenommen oder zu Unrecht keine Möglichkeit zur Teilnahme erhalten hat und (b) ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids dartun kann (<ref-law>). Das erforderliche rechtlich geschützte Interesse ergibt sich dabei nicht bereits aus dem verfassungsrechtlichen Willkürverbot oder dem Verhältnismässigkeitsgebot (vgl. <ref-ruling> E. 4; PETER UEBERSAX, Einreise und Anwesenheit, in: Uebersax/ Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2009, N. 7.147). Zur Willkürrüge ist eine Partei nur legitimiert, wenn sie sich auf eine gesetzliche Norm berufen kann, die ihr im Bereich der betroffenen und angeblich verletzten Interessen einen Rechtsanspruch einräumt oder zumindest den Schutz ihrer Interessen bezweckt (vgl. <ref-ruling> E. 6.1 S. 198).
1.3 Das Bundesamt für Migration verfügt die vorläufige Aufnahme, wenn der Vollzug der Weg- oder Ausweisung nicht möglich, nicht zulässig oder nicht zumutbar ist (Art. 83 Abs. 1 AuG). Diese "kann" von den kantonalen Behörden beantragt werden, nicht aber vom Betroffenen selber (Art. 83 Abs. 6 AuG; ZÜND/ARQUINT HILL, Beendigung der Anwesenheit, Entfernung und Fernhaltung, in: Ausländerrecht, a.a.O., N. 8.103). Sie ist keine Aufenthaltsbewilligung, sondern ein vorübergehender Status, der die Anwesenheit regelt, solange der Wegweisungsvollzug - d.h. die exekutorische Massnahme der Wegweisung zur Beseitigung des rechtswidrigen Zustands - nicht zulässig, nicht zumutbar oder nicht möglich erscheint (vgl. RUEDI ILLES, in: Caroni/Gächter/Thurnherr [Hrsg.], SHK Bundesgesetz über die Ausländerinnen und Ausländer [AuG], 2010, N. 2 f. zu Art. 83 AuG; SPESCHA/KERLAND/BOLZLI, Handbuch zum Migrationsrecht, 2008, S. 117 f.; PETER BOLZLI, in: Spescha/Thür/Zünd/Bolzli, Migrationsrecht, 3. Aufl. 2012, N. 1 ff. zu Art. 83 AuG). Der Beschwerdeführer macht geltend, die Vorinstanz habe in willkürlicher Weise verneint, dass bei ihm Wegweisungsvollzugshindernisse bestünden. Der Vollzug der Wegweisung sei ihm unzumutbar bzw. unzulässig. Auf seine Willkürrügen und den damit verbundenen Antrag, den Kanton anzuhalten, beim Bundesamt für Migration um eine vorläufige Aufnahme nachzusuchen, ist mangels eines entsprechenden Rechtsanspruchs nicht einzutreten (vgl. <ref-ruling> E. 3 S. 308 ff.).
1.4 Gegen den kantonalen Wegweisungsentscheid bzw. das Verneinen von Vollzugshindernissen durch die kantonalen Behörden kann mit der subsidiären Verfassungsbeschwerde hingegen an das Bundesgericht gelangt werden, soweit sich die betroffene ausländische Person dabei auf besondere verfassungsmässige Rechte beruft, die ihr unmittelbar ein rechtlich geschütztes Interesse im Sinne von <ref-law> verschaffen. Die entsprechenden Rügen müssen indessen jeweils rechtsgenügend begründet werden (Art. 116 i.V.m. <ref-law>); das Bundesgericht prüft die Verletzung von Grundrechten nicht von Amtes wegen, sondern nur soweit diese klar, sachbezogen und falls möglich belegt dargetan werden ("qualifizierte Rügepflicht"; vgl. <ref-ruling> E. 2.8 S. 494; <ref-ruling> E. 1.4.2 S. 254, 396 E. 3.1 S. 399). Soweit der Beschwerdeführer eine Verletzung besonderer verfassungsmässiger Rechte rechtsgenügend dartut (Art. 115-117 BGG), ist auf seine Eingabe einzutreten. Dies ist nicht der Fall hinsichtlich des in der Rechtsschrift erwähnten Art. 8 EMRK, der ohnehin die nicht Gegenstand des vorliegenden Verfahrens bildende Bewilligungsfrage betreffen würde.
2. 2.1 Der Beschwerdeführer rügt eine Verletzung des Anspruchs auf rechtliches Gehör dahin gehend, dass seine psychische Situation unrichtig gewürdigt worden sei, ebenso sei die Vorinstanz ihrer Pflicht zur weiteren Informationsbeschaffung bezüglich der aktuellen Verfolgungssituation in der Türkei nicht nachgekommen. Ihm sei gestützt auf Art. 29 und 30 Abs. 3 BV sowie Art. 6 EMRK eine mündliche Verhandlung zuzugestehen.
2.2 Unter die zulässige Geltendmachung von verfassungsmässigen Rechten fällt auch die Geltendmachung einer Gehörsverletzung (<ref-law>; Art. 6 EMRK), nicht jedoch eine allgemeine Anrufung des Untersuchungsgrundsatzes. Zum Anspruch auf rechtliches Gehör gehört das Recht des Betroffenen, sich vor Erlass eines in seine Rechtsstellung eingreifenden Entscheids zur Sache zu äussern sowie das Recht auf Abnahme der rechtzeitig und formrichtig angebotenen rechtserheblichen Beweismittel (<ref-ruling> E. 5.1 S. 293; <ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 2b S. 56; <ref-ruling> E. 2b S. 56). Indessen räumt <ref-law> keinen Anspruch auf eine mündliche Anhörung ein (<ref-ruling> E. 2.1 S. 428 f.). Auch steht die Verfassungsgarantie einer vorweggenommenen Beweiswürdigung nicht entgegen. Das Gericht kann auf die Abnahme von Beweisen verzichten, wenn es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür annehmen kann, seine Überzeugung werde durch weitere Beweiserhebungen nicht geändert (BGE <ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 3 S. 157). Anspruch auf eine mündliche Anhörung im Sinne von Art. 6 Ziff. 1 EMRK besteht, wenn der Beschwerdeführer die Verletzung von "civil rights" im Sinne der Konvention geltend machen kann.
2.3 Eine Gehörsverletzung ist im vorliegenden Verfahren nicht ersichtlich: Zum einen kann ein Wegweisungsverfahren nicht als zivilrechtliche Streitigkeit im Sinne von Art. 6 EMRK gelten; zum anderen durfte die Vorinstanz im Rahmen des fremdenpolizeilichen Wegweisungsverfahrens auf die mündliche Befragung und Würdigung der Umstände zu den Erkrankungen des Beschwerdeführers im Strafverfahren abstellen. Eine Gehörsverletzung liegt auch hinsichtlich der behaupteten unzulässigen Rückkehr in den Verfolgerstaat nicht vor: Die Vorinstanz durfte sich insbesondere auf die Stellungnahme des Bundesamtes für Migration als Fachbehörde stützen (vgl. dazu unten E. 4.3). Gerügt wird schliesslich noch, dass eine Gehörsverletzung auch dahin gehend bestehe, als die "besonderen Umstände" der Tatbegehung von der Vorinstanz nicht berücksichtigt worden seien. Auch diesem Vorbringen ist entgegenzuhalten, dass alle Umstände bezüglich der Tatbegehung im Rahmen des strafrechtlichen Verfahrens gewürdigt worden sind; im Rahmen des Wegweisungsverfahrens sind sie nicht mehr Verfahrensgegenstand. Eine Verletzung von <ref-law> liegt demnach nicht vor. Der angerufene <ref-law> schliesslich schreibt bloss vor, dass eine Gerichtsverhandlung öffentlich zu sein hat, wenn eine solche angeordnet worden ist; die Frage, ob eine mündliche öffentliche Verhandlung geboten ist, regelt diese Bestimmung nicht (<ref-ruling> E. 2.3-2.7 S. 291 ff.; vgl. auch Urteil 9C_833/2011 vom 24. Mai 2012 E. 5.1); auch diese Bestimmung ist demnach nicht verletzt.
3. 3.1 Der Beschwerdeführer sieht im Wegweisungsvollzug eine qualifizierte Verletzung der ihm als Flüchtling zustehenden verfassungsmässig geschützten Rechte: So stehe er unter dem Schutz des Rückschiebeverbots, insbesondere wiege seine Straftat nicht so schwer, dass sie jenen Schutz durchbrechen könnte; in seinem Heimatstaat drohe ihm zudem eine unmenschliche Behandlung i.S.v. Art. 3 EMRK.
3.2 Ein Flüchtling darf - unter Vorbehalt von <ref-law> (Non-Refoulement-Prinzip; Art. 33 Ziff. 1 FK; <ref-law>; vgl. unten E. 3.3) - 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. 2.2.1 S. 113; <ref-ruling> E. 3b S. 183; siehe auch FELLER/TÜRK/NICHOLSON, La protection des réfugiés en droit international, 2008, S. 133 ff.; ZÜND/ARQUINT HILL, in: Ausländerrecht, a.a.O., Rz. 8.89 ff.); insofern wird die Möglichkeit seiner Ausweisung flüchtlings- bzw. asylrechtlich beschränkt (<ref-ruling> E. 2.2 S. 113; 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).
Im Aufnahmestaat begangene Straftaten sind kein Grund zur Aberkennung der Flüchtlingseigenschaft. Der Betroffene bleibt, auch wenn das Bundesamt wegen einer besonders verwerflichen strafbaren Handlung das Asyl widerrufen hat (<ref-law>), im Genuss des ihm konventionsrechtlich gewährten völkerrechtlichen Schutzes, solange er materiell weiterhin als Flüchtling im Sinne von Art. 1 FK zu gelten hat. Dem Flüchtling ohne Asyl kommt demnach unter Umständen im international-flüchtlingsrechtlichen Kontext ein subsidiärer, zum Asyl komplementärer Schutz zu (vgl. Art. 83 Abs. 8 AuG; <ref-ruling> E. 2.2 S. 113; WALTER STÖCKLI, Asyl, in: Ausländerrecht, a.a.O., Rz. 11.48 und 11.77 ff.; PETER BOLZLI, in: Spescha/Kerland/Bolzli, Migrationsrecht, Zürich 2008, Vorbemerkungen zu Art. 83-88 sowie N. 26 zu Art. 83 AuG; RUEDI ILLES, Art. 83, in: STK AuG, a.a.O., N. 18 ff.).
3.3 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 (<ref-ruling> E. 2.2.2 S. 114; Urteil 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; NÄGELI/SCHOCH, Ausländische Personen als Straftäter und Straftäterinnen, in: Ausländerrecht, a.a.O., N. 22.212 ff.).
3.4 Der Beschwerdeführer ist in der Schweiz straffällig geworden, wobei sein Verschulden besonders schwer wiegt: Das Obergericht des Kantons Zürich hat ihn am 28. November 2003 wegen vorsätzlicher Tötung zu 8 Jahren Zuchthaus verurteilt, nachdem er am 23. Oktober 2001 seine Frau im Streit erschossen hatte. Der Beschwerdeführer hat mit dieser Tat massiv gegen die hiesigen strafrechtlichen und moralischen Normen verstossen. Vom Zürcher Obergericht wurde die besondere Kaltblütigkeit der Tat denn auch hervorgehoben; eine Subsumtion unter den Tatbestand des Mordes (<ref-law>) wurde erwogen, jedoch gestützt auf eine unzureichende Beweislage verneint. Mit seiner Tat hat der Beschwerdeführer die öffentliche Ordnung in schwerwiegender Weise gestört (<ref-law>); sein Asyl wurde denn auch rechtskräftig widerrufen (<ref-law>).
Der schwere Verstoss gegen die öffentliche Ordnung wird vom Beschwerdeführer anerkannt, er beruft sich jedoch auf seinen subsidiären internationalen völkerrechtlichen Schutz als Flüchtling: Aufgrund seiner psychischen Erkrankung sei es ihm nicht zumutbar, in seinen Heimatstaat ausgeschafft zu werden, weil die unerlässliche intensive medizinische Betreuung nicht gewährleistet sei; es drohe ihm diesbezüglich eine unmenschliche Behandlung, die gegen <ref-law> und Art. 3 EMRK verstosse (dazu nachfolgend E. 3.5). Ebenso sei er, weil er seine Frau umgebracht habe, im Falle einer Ausweisung der Rache ihrer Familie ausgesetzt: In der Türkei bestehe keine genügende polizeiliche Schutzinfrastruktur, um ihn vor Übergriffen von den Verwandten seiner Frau zu schützen, sodass bei einer Ausweisung gegen das Gebot, Flüchtlinge nicht in einen Staat auszuschaffen oder auszuliefern, in dem sie verfolgt werden, verstossen werde (<ref-law>; Art. 33 Abs. 1 FK; Non-Refoulement-Grundsatz; dazu nachfolgend E. 3.6).
3.5 Hinsichtlich der geltend gemachten gesundheitlichen Probleme ist darauf hinzuweisen, dass wegen solcher nur dann auf eine Unzumutbarkeit des Wegweisungsvollzugs geschlossen werden dürfte, wenn eine notwendige medizinische Behandlung im Heimatland fehlte und die Rückkehr zu einer raschen und lebensgefährlichen Beeinträchtigung des Gesundheitszustands führen würde (<ref-ruling> E. 4.3 S. 312). In Übereinstimmung mit den Feststellungen der Vorinstanz kann der Beschwerdeführer nicht dartun, dass aufgrund seiner psychischen Erkrankung sowie wegen der somatischen Probleme (Arbeitsunfall, Bluthochdruck) eine derart komplexe Situation vorliegt, welche im Falle einer Rückkehr in den Heimatstaat zu einer raschen und lebensgefährlichen Beeinträchtigung führte. Es ist davon auszugehen, dass die erforderliche, allenfalls stationäre psychiatrische Behandlung auch in der Türkei erfolgen kann, sodass keine unmenschliche Behandlung im Sinne von <ref-law> bzw. Art. 3 EMRK vorliegt.
3.6 Mit Bezug auf die behauptete Verfolgungssituation des Beschwerdeführers durch die Familie seiner Frau ist anzumerken, dass der Schutz des Non-Refoulement-Grundsatzes auf staatliche Verfolgung zielt. Inwieweit diese durch den behaupteten fehlenden polizeilichen Schutz, Sippenstreitigkeiten konsequent und landesweit zu verfolgen, gegeben ist, erscheint nicht hinreichend dargetan, sodass auf die Ausführungen der Vorinstanz zu verweisen ist: Es sind keine Gründe ersichtlich, weshalb sich der Beschwerdeführer nicht an einem anderen Ort als dem von Sippenfehden betroffenen Nurhak-Gebirge niederlassen könnte. Die Vorinstanz nimmt in ihrem Urteil explizit auch Bezug auf den Rekursentscheid des Regierungsrats vom 16. März 2011, wo festgestellt wird, dass sich Mitglieder der Familie mütterlicherseits in der Schweiz aufhalten oder aufgehalten haben und der Beschwerdeführer keinen Nachstellungen ausgesetzt war, sondern von jener Familie lediglich gemieden wird. Eine staatliche Verfolgungssituation, nach der es ausgeschlossen wäre, den Beschwerdeführer in die Türkei auszuweisen, ist in dieser Hinsicht nicht dargetan.
3.7 Im Aufnahmestaat begangene Straftaten sind - wie dargelegt - kein Grund zur Aberkennung der Flüchtlingseigenschaft, jedoch ist das Interesse der Schweiz, einen straffällig gewordenen Ausländer von der Schweiz fernzuhalten, in erster Linie anhand seines bisherigen Verhaltens und seines strafrechtlichen Verschuldens zu beurteilen; wesentlich ist dabei auch die im Strafverfahren erfolgte Einschätzung der Rückfallgefahr (<ref-ruling> E. 4.2 S. 118 f.). Im Strafverfahren wurde der Beschwerdeführer als erheblich rückfallgefährdet eingeschätzt; eine ambulante Massnahme wurde als unzureichend angesehen; vielmehr war eine "lange andauernde stationäre Therapie" in einer psychiatrischen Klinik empfohlen, die mit der Urteilsfällung im Sinne einer stationären Massnahme (<ref-law>) angeordnet wurde; infolge der weiter bestehenden Möglichkeit eines Rückfalls bildet der Beschwerdeführer eine Gefahr für die Öffentlichkeit. Für die Beurteilung kann zudem nicht entscheidend sein, dass der Beschwerdeführer, dem nach seiner Tat die Freiheit entzogen war, tatsächlich keine weiteren Delikte verübt hat. Gestützt auf die rechtskräftige Verurteilung wegen des besonders schweren Verbrechens und die im Strafverfahren bzw. Straf- und Massnahmevollzug zusätzlich festgestellte fehlende Einsichtsfähigkeit hinsichtlich der Tat, der weiterhin massiven Verfolgungsideen und der damit konkreten Wiederholungsgefahr, ist der Beschwerdeführer als gemeingefährlich zu bezeichnen, weshalb das Rückschiebungsverbot seiner Wegweisung nicht entgegensteht (E. 3.3 hievor; vgl. <ref-law>; Art. 33 Abs. 2 FK; Urteil 2A.51/2006 vom 8. Mai 2006 E. 4.1).
4. 4.1 Der Beschwerdeführer macht nach wie vor eine akute Gefahr von Folterungen geltend, aufgrund deren er als Flüchtling anerkannt worden sei: Wenn er nach mehr als 20 Jahren Abwesenheit ohne Nachricht wieder an die Türkei ausgeliefert werde, drohe ihm als ehemaligem Sympathisanten der Kommunistischen Partei noch immer eine unmenschliche Behandlung oder Bestrafung, indem er erneut Folterungen ausgesetzt werden könnte (<ref-law>; Art. 3 Abs. 1 Folterschutzkonvention; Art. 7 und 10 Ziff. 1 UNO-Pakt II).
4.2 In Bezug auf das vom Beschwerdeführer angerufene Folterverbot gilt keine Ausnahme vom Rückschiebeverbot (vgl. die Urteile des EGMR Ahmed gegen Österreich vom 17. Dezember 1996, Recueil CourEDH 1996-VI S. 2195 Ziff. 46; Chahal gegen Grossbritannien vom 15. November 1996, Recueil CourEDH 1996-V S. 1831 Ziff. 79 f. und 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 Folterschutzkonvention; Urteil 2A.313/2005 vom 25. August 2005 E. 2.2).
4.3 Gemäss der Feststellung der Vorinstanz haben der Beschwerdeführer selber oder zumindest seine Kinder vor über 20 Jahren der Kommunistischen Partei der Türkei nahe gestanden. Dem Asylgesuch des Beschwerdeführers wurde primär entsprochen, weil zuvor zweien seiner Kinder Asyl gewährt wurde, die mittlerweile jedoch auf diesen Status verzichtet haben, um wieder in die Türkei reisen zu können. Das Bundesamt für Migration hat diesen Umstand als ein starkes Indiz gewertet, dass die Familie unterdessen nicht mehr akut verfolgt wird, und ist daher am 20. März 2009 zur Auffassung gelangt, dass dem Beschwerdeführer keine Nachteile mehr in seinem Heimatland drohten. Auf diese Einschätzung des Bundesamtes für Migration als Fachbehörde durfte sich die Vorinstanz stützen. Dem Beschwerdeführer gelingt es nicht, konkret darzutun, weshalb ihm noch heute Folter oder andere Nachteile drohen könnten; es sind auch keine Gründe dargetan, weshalb sich die der Einschätzung des Bundesamtes für Migration von 2009 zugrunde gelegten Umstände unterdessen wesentlich geändert haben könnten. Im Gegenteil ist davon auszugehen, dass sich die Menschenrechtssituation in der Türkei vor dem Hintergrund der Beitrittsverhandlungen zur EU verbessert hat. Aus den allgemeinen Ausführungen des Beschwerdeführers zur Situation vor über 20 Jahren ist eine aktuelle Foltergefährdung nicht dargetan (Erfordernis des "real risk"; Urteil 2C_87/2007 vom 18. Juni 2007 E. 4.3.2).
5. Die Beschwerde ist somit abzuweisen, soweit darauf eingetreten werden kann.
Da sich die Verfassungsbeschwerde nicht als aussichtslos erweist und der Beschwerdeführer bedürftig ist, kann die beantragte unentgeltliche Rechtspflege bewilligt und auf die Erhebung von Gerichtskosten verzichtet werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
2.1 Es werden keine Kosten erhoben.
2.2 Dem Beschwerdeführer wird Rechtsanwalt Peter Frei als Rechtsbeistand beigegeben. Diesem wird aus der Gerichtskasse eine Entschädigung von Fr. 2'000.-- ausgerichtet.
3. Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, schriftlich mitgeteilt.
Lausanne, 2. August 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Hänni