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. 