Sachverhalt:
A. Das Obergericht des Kantons Zürich verurteilte X._ am 11. Dezember 2007 wegen versuchter schwerer Körperverletzung, Gefährdung des Lebens, Vergehens gegen das Waffengesetz, mehrfacher einfacher Körperverletzung sowie mehrfacher Übertretung des Betäubungsmittelgesetzes zu einer Gesamtfreiheitsstrafe von 4 Jahren und 1 Monat, abzüglich 325 Tage erstandener Untersuchungshaft bzw. vorzeitigem Strafvollzug, und zu einer Busse von Fr. 200.--. Der Vollzug der Freiheitsstrafe wurde nicht aufgeschoben. Das Obergericht ordnete eine ambulante Massnahme (zur Behandlung der Sucht und der psychischen Störung) während des Strafvollzugs an.
X._ trat die Strafe am 11. Dezember 2007 an. Das Strafende fiel auf den 9. März 2011. Am 20. Dezember 2010 verfügte das Amt für Justizvollzug des Kantons Zürich (JUV) die bedingte Entlassung von X._ aus dem Strafvollzug per 5. Januar 2011. Er sollte in das Therapiezentrum Lehn in Kriens zum Zweck der Suchtbehandlung übertreten. Das JUV erteilte ihm entsprechende Weisungen. Nach nur wenigen Tagen schloss das Therapiezentrum Lehn X._ wegen Drogenkonsums aus. Er wurde zur Verhaftung ausgeschrieben. Am 21. Januar 2011 ordnete das Zwangsmassnahmengericht des Bezirks Zürich die Sicherheitshaft an.
Am 27. Januar 2011 beantragte das JUV gestützt auf <ref-law> die nachträgliche Anordnung einer kombinierten stationären Massnahme (Behandlung einer psychischen Störung und Suchtbehandlung). Mit Urteil vom 15. März 2011 ordnete das Bezirksgericht Zürich nach Anhörung des Betroffenen eine stationäre Suchtbehandlung im Sinne von <ref-law> unter Aufschub des Vollzugs der Reststrafe an. Dagegen erhob X._ Beschwerde. Das Obergericht des Kantons Zürich beschloss am 2. September 2011, über X._ ein Ergänzungsgutachten einzuholen, und verlängerte die Sicherheitshaft bis einstweilen 18. Januar 2012.
Nach Eingang des psychiatrischen Gutachtens vom 25. Oktober 2011, welches den Parteien zur Stellungnahme unterbreitet wurde, wies das Obergericht des Kantons Zürich mit Beschluss vom 17. Januar 2012 die Beschwerde von X._ ab und bestätigte die nachträgliche Anordnung einer stationären Suchtbehandlung im Sinne von <ref-law>. Gleichzeitig wurde X._ mittels Verfügung der vorzeitige Massnahmeantritt bewilligt und die Sicherheitshaft bis zum Antritt der stationären Massnahme bzw. bis einstweilen maximal 18. April 2012 verlängert.
B. Mit Beschwerde in Strafsachen beantragt X._, der Beschluss und die Verfügung des Obergerichts des Kantons Zürich vom 17. Januar 2012 seien aufzuheben und die Sache im Sinne der Erwägungen an die Vorinstanz zurückzuweisen. Er sei sofort aus der Sicherheitshaft zu entlassen. Die Kosten des Verfahrens seien dem Kanton Zürich aufzuerlegen, welcher zu verpflichten sei, ihm eine angemessene Entschädigung zu bezahlen. X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung.
C. Das Obergericht des Kantons Zürich und die Oberstaatsanwaltschaft des Kantons Zürich verzichteten am 5. April bzw. 13. April 2012 auf eine Vernehmlassung. Das JUV hat sich nicht vernehmen lassen.

Erwägungen:
1. Der Beschwerdeführer rügt, die nachträgliche Anordnung der stationären Suchtbehandlung verletze Art. 5 Abs. 1 lit. a EMRK. Er verneint eine Anbindung der Anordnung der stationären Massnahme an das ursprüngliche Urteil vom 11. Dezember 2007 und beruft sich auf das Urteil des Europäischen Gerichtshofes (EGMR) vom 13. Januar 2011 in der Rechtssache Haidn gegen Deutschland. Im obergerichtlichen Urteil vom 11. Dezember 2007 sei neben der Freiheitsstrafe (nur) eine ambulante vollzugsbegleitende Massnahme angeordnet worden. Die Möglichkeit zur Umwandlung in eine stationäre Behandlung sei im besagten Urteil nicht ausdrücklich vorbehalten worden. Die nachträgliche Anordnung dieser Massnahme bilde mithin eine neue und eigenständige Freiheitsentziehung ohne entsprechende Urteilsgrundlage und sei damit konventionswidrig (Beschwerde, S. 4 - 9).
1.1 Das Obergericht des Kantons Zürich verurteilte den Beschwerdeführer am 11. Dezember 2007 zu einer Freiheitsstrafe und ordnete eine vollzugsbegleitende ambulante Massnahme im Sinne von <ref-law> an. Es stützte sich auf das psychiatrische Gutachten von Dr. med. A._ vom 30. Mai 2007. Darin wurde dem Beschwerdeführer eine hohe Rückfallgefahr für die Begehung von Gewalthandlungen im Sinne schwerer Körperverletzungen attestiert und aufgrund des Einsatzes massiver Gewalt im Sinne tötungsnaher Handlungen auch eine relevante Gefahr für Gewalthandlungen mit Todesfolge bejaht. Der Gutachter empfahl in erster Linie die Anordnung einer ambulanten Massnahme während des Strafvollzugs. Eine Anstaltsbehandlung erachtete er seinerzeit (noch) nicht als notwendig, wies jedoch ausdrücklich darauf hin, dass eine Umwandlung in eine stationäre Massnahme zu prüfen wäre, falls die ambulante Behandlung keine ausreichende Senkung der Rückfallgefahr bewirken könnte (kantonale Akten, Gutachten, act. HD 8/3, S. 50 ff.). Am 15. März 2011 ordnete das Bezirksgericht Zürich gestützt auf <ref-law> die Umwandlung der bisherigen ambulanten Massnahme in eine stationäre Suchtbehandlung unter Aufschub des Vollzugs der Reststrafe an. Die Vorinstanz bestätigt am 17. Januar 2012 die Massnahmeänderung. Sie stellt auf das ursprüngliche psychiatrische Gutachten vom 30. Mai 2007 und das psychiatrische Ergänzungsgutachten vom 25. Oktober 2011 ab. In Letzterem wird die vom Beschwerdeführer ausgehende Rückfallgefahr für schwere Gewalthandlungen trotz Therapieerfolgen im Rahmen der ambulanten Behandlung noch immer als deutlich ausgeprägt eingestuft (kantonale Akten, Ergänzungsgutachten, act. 39, S. 23, 25). Der Experte hält unter Verweis auf seine Ausführungen im Gutachten vom 30. Mai 2007 ein stationäres Setting im Sinne von <ref-law> nunmehr für indiziert (kantonale Akten, Ergänzungsgutachten, act. 39, S. 24). Die Vorinstanz bejaht den Kausalzusammenhang zwischen ursprünglicher Verurteilung vom 11. Dezember 2007 und neuerlicher Freiheitsentziehung infolge Massnahmeänderung (Entscheid, S. 12-15).
1.2 Die verschiedenen Massnahmen nach <ref-law> sind wechselseitig austauschbar. Nach der Praxis des Bundesgerichts kann grundsätzlich jede Massnahme in eine andere umgewandelt werden (<ref-ruling>). Damit wird dem Bedürfnis nach Flexibilität und Durchlässigkeit im Massnahmenrecht Rechnung getragen. Massnahmen werden ohne Rücksicht auf Art und Dauer der ausgesprochenen Strafe angeordnet. Massgebend sind insoweit einzig der Geisteszustand des Täters und die Auswirkungen der Massnahme auf die Gefahr weiterer Straftaten. Wenn das Ziel einer ambulanten Massnahme in Freiheit oder während des Strafvollzugs nicht erreicht wird, kommt bei gegebenen Voraussetzungen die Umwandlung in eine stationäre Massnahme in Betracht (<ref-ruling> E. 2.3; <ref-ruling> E. 2.3.2 mit Hinweisen; siehe auch Urteil 6B_375/2008 vom 21. Oktober 2008 E. 3.1; Urteil 6B_160/2010 vom 1. Juni 2010 E. 1.2). Der Beschwerdeführer macht zu Recht nicht geltend, dass die Umwandlung der ambulanten Therapie in eine stationäre Suchtbehandlung gestützt auf <ref-law> Bundesrecht verletzt.
1.3 Im Rahmen der späteren Anordnung von Massnahmen ist Art. 5 EMRK zu beachten. Gemäss Abs. 1 lit. a der Konventionsbestimmung muss eine Sanktion auf einer gerichtlichen Verurteilung beruhen ("sufficient causal connection"). Die spätere Anpassung der Massnahme ist nur rechtsgenügend abgestützt, wenn die ursprüngliche Verurteilung und der später angeordnete beziehungsweise abgeänderte Freiheitsentzug hinreichend miteinander zusammenhängen. Es bedarf insoweit einer zeitlichen und inhaltlichen Verknüpfung zwischen Verurteilung und Freiheitsentziehung. Massgeblich ist damit, ob die spätere Sanktion vom ursprünglichen Zweck der ersten Verurteilung inhaltlich noch getragen wird (<ref-ruling> E. 3.3 mit Hinweisen auf Rechtsprechung und Lehre; JOCHEN ABR. FROWEIN/WOLFGANG PEUKERT, EMRK-Kommentar, 3. Aufl., 2009, Art. 5 N 48; CHRISTOPH GRABENWARTER/ KATHARINA PABEL, Europäische Menschenrechtskonvention, 5. Aufl., 2011, S. 196; JENS MEYER-LADEWIG, Europäische Menschenrechtskonvention, Handkommentar, 3. Aufl., 2011, Art. 5 Rz. 25 ff., S. 96).
1.4 Die mit der Umwandlung in eine stationäre Suchtbehandlung zusammenhängende Freiheitsentziehung des Beschwerdeführers beruht auf dem Urteil vom 11. Dezember 2007. Mit der Anordnung der ambulanten Therapie wurde die spätere Abänderung dieser Massnahme implizit vorbehalten. Das ergibt sich aus dem im Massnahmerecht geltenden System der Durchlässigkeit zwischen den einzelnen Sanktionen und aus dem Umstand, dass im Zeitpunkt einer Massnahmeanordnung nicht sicher vorausgesagt werden kann, ob die als zweckmässig erachtete Massnahme auch tatsächlich zielführend sein wird. Oft stellt sich erst im Vollzug heraus, welche Behandlung des Täters im Hinblick auf eine Aufhebung bzw. Verringerung der Gefährlichkeit am ehesten geeignet erscheint. Der Sachverständige wies im Gutachten vom 30. Mai 2007 auf diese Problematik hin und hielt ausdrücklich fest, dass bei einem allfälligen Misserfolg der ambulanten Therapie eine Umwandlung in eine stationäre Behandlung zu prüfen sei. Der gerichtliche Massnahmeentscheid stützt sich auf das Gutachten. Die Ausführungen des Sachverständigen zur Abänderung der Massnahme bei Unzweckmässigkeit der angeordneten ambulanten Therapie sind damit vom Gericht gewürdigt und implizit ins Urteil aufgenommen worden. Hinzu kommt, dass die Möglichkeit der späteren Umwandlung der ambulanten in eine stationäre Behandlung ausdrücklich Thema anlässlich der damaligen Berufungsverhandlung bildete (vgl. kantonale Akten, act. 33, Plädoyer Angeschuldigter, S. 7 f.). Die Option einer späteren Abänderung der ambulanten Massnahme ist damit im Urteil vom 11. Dezember 2007 mit enthalten. Die nachträgliche Anordnung der stationären Suchtbehandlung konkretisiert mithin lediglich den Massnahmevollzug, wie er bereits damals - bei Unzweckmässigkeit der ambulanten Therapie - vorgezeichnet war. Dass die Möglichkeit einer späteren Massnahmeänderung in den Urteilserwägungen nicht ausdrücklich erwähnt wird, ist nicht massgeblich. Das Urteil des EGMR in Sachen Haidn gegen Deutschland vom 13. Januar 2011 (Nr. 6587/2004) ist gemäss den zutreffenden Erwägungen der Vorinstanz nicht einschlägig. In jenem Urteil wurde ein hinreichender Kausalzusammenhang zwischen ursprünglicher Verurteilung und nachträglicher Unterbringung im Gefängnis zu Präventionszwecken verneint, weil im Ausgangsurteil vom März 1999 nur eine Freiheitsstrafe ausgesprochen worden war und eine Unterbringung zu Präventionszwecken nach der damaligen Rechtslage nicht hätte angeordnet werden können, da das entsprechende Gesetz zur Unterbringung von besonders rückfallgefährdeten hochgefährlichen Straftätern erst im Januar 2002 in Kraft trat. Mangels Vergleichbarkeit der Rechtslagen kann der Beschwerdeführer aus diesem Urteil nichts für sich ableiten.
1.5 Aus den gleichen Gründen ist mit der Vorinstanz die vom Beschwerdeführer geltend gemachte Verletzung des Grundsatzes "ne bis in idem" zu verneinen (Beschwerde, S. 8 f.; Entscheid, S. 15). Nach diesem Grundsatz darf ein Beschuldigter nicht wegen derselben Tat mehrmals verfolgt und bestraft werden (vgl. Art. 4 des Protokolls Nr. 7 zur EMRK vom 22. November 1984 [SR 0.101.07]; Art. 14 Abs. 7 IPBPR [SR 0.103.2]; <ref-ruling> E. 5; <ref-ruling> E. 2b). Mit der nachträglichen Umwandlung der ambulanten Massnahme in eine stationäre Suchtbehandlung liegt keine zweimalige Verurteilung in der gleichen Sache vor. Die neue Freiheitsentziehung infolge Massnahmeänderung aufgrund der fortbestehenden, deutlich ausgeprägten Rückfallgefahr für schwere Gewalthandlungen ist durch die ursprüngliche Verurteilung vom 11. Dezember 2007 inhaltlich gedeckt (vgl. Urteile des Bundesgerichts 6S.297/2006 vom 26. September 2006 E. 2.3 und 6B_237/2008 vom 20. Juni 2008 E. 2.2).
1.6 Unbegründet ist auch das Vorbringen des Beschwerdeführers, die Vorinstanz habe das Gesuch um Entlassung aus der Sicherheitshaft zu Unrecht abgewiesen (Beschwerde, S. 3, 9 f.). Der Beschwerdeführer wurde am 21. Januar 2011 in Sicherheitshaft (Art. 229 StPO) versetzt und zwar im Hinblick auf das durchzuführende Nachverfahren im Sinne von <ref-law> (kantonale Akten, act. 146). Die damalige Annahme des Zwangsmassnahmengerichts, es sei hinreichend wahrscheinlich, dass das Verfahren zur Anordnung einer freiheitsentziehenden Massnahme führe, welche die Sicherstellung und Zurückbehaltung des Beschwerdeführers nötig machte (vgl. kantonale Akten, act. 146), bestätigte sich. Die Vorinstanz ordnete die stationäre Suchtbehandlung im Sinne von <ref-law> i.V.m. <ref-law> zu Recht an. Damit erweist sich auch die Anordnung der Sicherheitshaft als rechtmässig. Es kann auf die zutreffenden Ausführungen im angefochtenen Entscheid verwiesen werden (Entscheid, S. 21). Auf das Gesuch des Beschwerdeführers, er sei unverzüglich aus der Sicherheitshaft zu entlassen, kann das Bundesgericht mangels Zuständigkeit nicht eintreten. Aus dem gleichen Grund ist auf das Begehren der Oberstaatsanwaltschaft des Kantons Zürich um Verlängerung der Sicherheitshaft (act. 21) nicht einzugehen. Die Einreichung einer Beschwerde ans Bundesgericht hat nicht zur Folge, dass die Zuständigkeit der Haftentlassung oder Haftverlängerung den kantonalen Behörden entzogen und auf das Bundesgericht übertragen würde. Dass der Beschwerde in Strafsachen gemäss <ref-law> von Gesetzes wegen aufschiebende Wirkung zukommt, wenn sie sich gegen einen Entscheid richtet, der eine unbedingte Freiheitsstrafe oder eine freiheitsentziehende Massnahme anordnet, ändert daran nichts, da dadurch nur die Vollstreckbarkeit des formell rechtskräftigen Urteils aufgeschoben wird.
1.7 Die Vorinstanz (oder die zuständige Vollzugsbehörde) wird damit über die weitere Inhaftierung des Beschwerdeführers zu befinden haben. Sie hat dafür Sorge zu tragen, dass der Beschwerdeführer ohne weiteren Verzug in einer für die Suchtbehandlung im Sinne von <ref-law> geeigneten Einrichtung untergebracht werden kann. Die notwendigen Schritte hierfür wurden bereits unternommen. Das Massnahmezentrum St. Johannsen hat sich gemäss Vorinstanz bereit erklärt, den Beschwerdeführer in die "Triage-Abteilung" aufzunehmen. Er befinde sich derzeit auf Platz 3 der Warteliste (Entscheid, S. 22 mit Verweis auf Protokoll, S. 21).
2. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Dem Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann stattgegeben werden (<ref-law>). Es sind folglich keine Kosten zu erheben, und der Rechtsvertreter des Beschwerdeführers ist aus der Bundesgerichtskasse angemessen zu entschädigen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen. Dem Beschwerdeführer wird Rechtsanwalt Dr. Thomas Fingerhuth als unentgeltlicher Rechtsbeistand beigegeben.
3. Es werden keine Kosten erhoben.
4. Dem Rechtsvertreter des Beschwerdeführers wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- aus der Bundesgerichtskasse ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 18. April 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill