Sachverhalt:
A. Das Appellationsgericht des Kantons Basel-Stadt sprach den am 10. März 1982 geborenen X._ am 12. Januar 2007 im Berufungsverfahren des qualifizierten Raubes, der Gefährdung des Lebens, der einfachen Körperverletzung mit einem gefährlichen Gegenstand, der versuchten einfachen Körperverletzung mit einem gefährlichen Gegenstand, der Nötigung, der versuchten Nötigung, der mehrfachen Hehlerei, der Widerhandlung gegen das Betäubungsmittelgesetz, der einfachen und groben Verletzung von Verkehrsregeln sowie der mehrfachen Widerhandlung gegen das Waffengesetz schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von 8 Jahren. Gleichzeitig widerrief es den bedingten Aufschub des Vollzugs einer vom Strafgericht des Kantons Basel-Stadt am 2. Mai 2001 ausgesprochenen Gefängnisstrafe von 12 Monaten (wegen mehrfachen, teilweise versuchten Raubes und versuchter Nötigung).
Die von X._ dagegen erhobene Beschwerde (Schuldpunkt, Strafzumessung) wies das Bundesgericht am 12. Mai 2007 ab (Verfahren 6B_48/2007).
B. X._ verbüsste seine Strafe in der Strafanstalt Bostadel. Er ersuchte am 4. Juli 2007 um Vollzugslockerungen. Die Interkantonale Fachkommission zur Beurteilung der Gemeingefährlichkeit von Straftätern der Kantone Solothurn, Basel-Landschaft und Basel-Stadt (IFKGS) stufte ihn am 29. Oktober 2007 als gemeingefährlich ein. Hinweise auf eine Krankheit oder eine Persönlichkeitsstörung schloss die IFKGS aus.
Das Justiz- und Sicherheitsdepartement (JSD) des Kantons Basel-Stadt gab auf Empfehlung der IFKGS ein Gutachten beim Forensisch-Psychiatrischen Dienst (FPD) der Universität Bern in Auftrag. Gemäss Gutachten vom 24. September 2008 leidet X._ an einer schwer zu behandelnden paranoiden und narzisstischen Persönlichkeitsstörung, welche bereits im Tatzeitpunkt bestanden hat. Die von ihm ausgehende Rückfallgefahr wurde als erheblich und die Legalprognose insgesamt als sehr ungünstig eingestuft. Es seien mit hoher Wahrscheinlichkeit namentlich Raubstraftaten zu erwarten, wobei es zu Gewalttaten gegenüber den Opfern kommen könne, wenn sich diese wehrten. Dass es insofern auch zu einer Tötung kommen könnte, sei nicht ausgeschlossen. Es sei jedoch nicht davon auszugehen. Am 10. November 2008 stufte die IFKGS X._ erneut als gemeingefährlich ein.
Am 30. Dezember 2008 stellte das JSD dem Appellationsgericht den Antrag auf Prüfung der nachträglichen Anordnung einer vollzugsbegleitenden psychotherapeutischen ambulanten Behandlung. Das Appellationsgericht des Kantons Basel-Stadt wies diesen Antrag am 4. Dezember 2009 ab. Für die nachträgliche Anordnung einer ambulanten Behandlung bestünde keine gesetzliche Grundlage. Es warf die Frage auf, ob nicht allenfalls eine stationäre Behandlung im Sinne von <ref-law> in Betracht zu ziehen wäre, und regte für diesen Fall die Einholung eines Ergänzungsgutachtens an.
Namentlich gestützt auf das beim FPD der Universität Bern eingeholte Ergänzungsgutachten vom 30. Juni 2010 beantragte das JSD am 7. Juli 2010 die Prüfung der nachträglichen Anordnung einer Verwahrung gemäss <ref-law>, wobei auch die Möglichkeit der nachträglichen Anordnung einer stationären Massnahme nach <ref-law> nicht ausgeschlossen werden sollte.
Das Appellationsgericht des Kantons Basel-Stadt ordnete am 6. Mai 2011 über X._ nachträglich eine Verwahrung im Sinne von <ref-law> an.
C. Das Bundesgericht hiess die von X._ dagegen erhobene Beschwerde mit Urteil vom 30. Januar 2012 teilweise gut und wies die Angelegenheit an die Vorinstanz zurück. Es bejahte die Revisionsvoraussetzungen, hielt aber die Anordnung der Verwahrung gemäss <ref-law> i.V.m. <ref-law> für bundesrechtswidrig. Es sei zu prüfen, ob eine stationäre therapeutische Massnahme im Sinne von <ref-law> i.V.m. <ref-law> anzuordnen sei (6B_487/2011).
Am 22. August 2012 ordnete das Appellationsgericht des Kantons Basel-Stadt über X._ eine stationäre therapeutische Massnahme im Sinne von <ref-law> i.V.m. <ref-law> an.
D. X._ führt Beschwerde in Strafsachen. Er beantragt, es sei festzustellen, dass das Appellationsgericht für die nachträgliche Anordnung einer stationären Massnahme nach <ref-law> nicht zuständig sei. Das Verfahren sei dem erstinstanzlichen Strafgericht des Kantons Basel-Stadt zu überweisen. Eventualiter sei der Entscheid vom 22. August 2012 aufzuheben und festzustellen, dass die Voraussetzungen von <ref-law> nicht gegeben seien und er nach Verbüssung der Strafe aus dem Vollzug zu entlassen sei. X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung.
E. Das Appellationsgericht des Kantons Basel-Stadt beantragt gestützt auf die Begründung seines Entscheids vom 22. August 2012 die Abweisung der Beschwerde. Das JSD hat auf eine Stellungnahme zur Beschwerde verzichtet.

Erwägungen:
1. Der bundesgerichtliche Rückweisungsentscheid erging am 30. Januar 2012 und somit nach dem Inkrafttreten der schweizerischen Strafprozessordnung am 1. Januar 2011. Auf das neue Verfahren ist die StPO anwendbar (<ref-law>), welche im Übrigen bereits für das bisherige Verfahren galt. Das JSD leitete am 7. Juli 2010 das nachträgliche Verfahren zur Prüfung einer sichernden Massnahme ein. Sie beantragte im Hauptstandpunkt die nachträgliche Anordnung einer Verwahrung im Sinne von <ref-law>, eventuell die Anordnung einer stationären Massnahme nach <ref-law>. Die Vorinstanz fällte das Urteil am 6. Mai 2011. Bei Inkrafttreten der StPO war das Verfahren bereits hängig und richtete sich in Anwendung von <ref-law> i.V.m. 451 StPO nach neuem Recht.
2. 2.1 Der Beschwerdeführer stellt die Zuständigkeit der Vorinstanz in Frage. Für die nachträgliche Anordnung einer stationären therapeutischen Massnahme nach <ref-law> sei nach <ref-law> das erstinstanzliche (Straf-)Gericht kompetent. Es sei nicht einsehbar, weshalb gerade im Zusammenhang mit der späteren Anordnung einer solch einschneidenden Massnahme ein Instanzenverlust hinzunehmen sei (vgl. Beschwerde, S. 10 ff.).
2.2 Die Vorinstanz teilt die Ansicht des Beschwerdeführers nicht. Es liege kein Anwendungsfall von <ref-law> vor. Das konkrete Verfahren sei durch den Antrag der Vollzugsbehörde auf Prüfung der nachträglichen Anordnung einer Verwahrung, eventuell einer stationären therapeutischen Massnahme eingeleitet worden. Für die nachträgliche Anordnung der Verwahrung sei sie - die Vorinstanz - als Berufungsgericht zuständig (<ref-law> i.V.m. Art. <ref-law> i.V.m. § 18 Abs. 1 und 4 des kantonalen Einführungsgesetzes zur Strafprozessordnung [EG StPO/BS]). Bei der Prüfung, ob ein Täter nachträglich verwahrt werden müsse, sei unter anderem abzuklären, ob er behandelbar sei. Die Anordnung der Verwahrung nach <ref-law> setze Therapieunfähigkeit voraus. Komme das Gericht zum Schluss, dass die Gefahr weiterer Straftaten nach <ref-law> durch eine Therapie in der Regel innert 5 Jahren deutlich verringert werden könne, dürfe es keine Verwahrung aussprechen, sondern müsse es gegebenenfalls eine stationäre therapeutische Massnahme nach <ref-law> anordnen. Hierfür sei und bleibe das Gericht zuständig, welches die Prüfung der Verwahrung nach <ref-law> i.V.m. <ref-law> vorgenommen habe. Daraus ergebe sich die Zuständigkeit der Vorinstanz (Entscheid, S. 4 f.).
2.2 Die Vorinstanz teilt die Ansicht des Beschwerdeführers nicht. Es liege kein Anwendungsfall von <ref-law> vor. Das konkrete Verfahren sei durch den Antrag der Vollzugsbehörde auf Prüfung der nachträglichen Anordnung einer Verwahrung, eventuell einer stationären therapeutischen Massnahme eingeleitet worden. Für die nachträgliche Anordnung der Verwahrung sei sie - die Vorinstanz - als Berufungsgericht zuständig (<ref-law> i.V.m. Art. <ref-law> i.V.m. § 18 Abs. 1 und 4 des kantonalen Einführungsgesetzes zur Strafprozessordnung [EG StPO/BS]). Bei der Prüfung, ob ein Täter nachträglich verwahrt werden müsse, sei unter anderem abzuklären, ob er behandelbar sei. Die Anordnung der Verwahrung nach <ref-law> setze Therapieunfähigkeit voraus. Komme das Gericht zum Schluss, dass die Gefahr weiterer Straftaten nach <ref-law> durch eine Therapie in der Regel innert 5 Jahren deutlich verringert werden könne, dürfe es keine Verwahrung aussprechen, sondern müsse es gegebenenfalls eine stationäre therapeutische Massnahme nach <ref-law> anordnen. Hierfür sei und bleibe das Gericht zuständig, welches die Prüfung der Verwahrung nach <ref-law> i.V.m. <ref-law> vorgenommen habe. Daraus ergebe sich die Zuständigkeit der Vorinstanz (Entscheid, S. 4 f.).
2.3 2.3.1 Nachträgliche Entscheide sind in einem gesonderten selbstständigen Verfahren zu treffen. Zuständig für solche Nachverfahren ist - soweit der Entscheid einer richterlichen Behörde übertragen ist und nicht eine erneute Straffälligkeit Grund für die nachträgliche Änderung oder Ergänzung des Urteils bildet - nach <ref-law> in der Regel das Gericht, welches den erstinstanzlichen Entscheid gefällt hat (Marianne Heer, in: Schweizerische Strafprozessordnung, Basler Kommentar, 2011, N. 6 zu Art. 363; Niklaus Schmid, Handbuch des Schweizerischen Strafprozessrechts, 2009, S. 636 N. 1390; Niklaus Oberholzer, Grundzüge des Strafprozessrechts, 2012, S. 528, N. 1504). Das gilt auch, wenn im Rahmen eines Berufungsverfahrens das Berufungsgericht das erstinstanzliche Urteil überprüft und ein neues Urteil gefällt hat (statt vieler Oberholzer, a.a.O., S. 529, N. 1504).
2.3.2 Für die nachträgliche Massnahmeanordnung im Sinne von <ref-law> ist in Anwendung von <ref-law> somit grundsätzlich das Gericht zuständig, welches erstinstanzlich das ursprüngliche Strafurteil gefällt hat (vgl. auch die Übergangsbestimmung gemäss <ref-law>). Die Zuständigkeitsregelung im StGB ergibt nichts Abweichendes. Darin wird das Gericht für zuständig erklärt, welches die Strafe ausgesprochen oder die Verwahrung angeordnet hat (<ref-law>). Nach der Botschaft des Bundesrats zur Änderung des Schweizerischen Strafgesetzbuches (BBl 1999 II 1979 ff., S. 2100) handelt es sich um das Gericht, welches das Urteil gefällt hat. Ob damit das erst- oder aber das zweitinstanzliche Gericht gemeint ist, lässt sich dem Wortlaut von <ref-law> nicht eindeutig entnehmen (Urteil 6B_252/2010 vom 22. Juni 2010 E. 1.2), weshalb unter Vorbehalt einer abweichenden kantonalen Regelung auf die StPO abzustellen ist (ähnlich Heer, a.a.O., N. 7 zu <ref-law>, welche gestützt auf <ref-law> zwar grundsätzlich das Berufungsgericht für zuständig erachtet, im Ergebnis aber <ref-law> vorgehen lässt; vgl. auch Stratenwerth/Wohlers, Schweizerisches Strafgesetzbuch, Handkommentar, 2013, N. 3 zu Art. 65, und Trechsel/Pauen, Schweizerisches Strafgesetzbuch, Praxiskommentar, 2013, N. 4 zu Art. 65, welche mit anderer Begründung zum gleichen Ergebnis gelangen, indem sie gestützt auf <ref-law> das Gericht für zuständig halten, welches die "erste" Verurteilung ausgesprochen hat.).
2.3.3 Die nachträgliche Anordnung einer Verwahrung im Sinne von <ref-law> stellt einen Sonderfall dar. Es gilt eine von <ref-law> abweichende Regelung (Christian Schwarzenegger, in: Kommentar zur Schweizerischen Strafprozessordnung [StPO], 2010, N. 3 zu Art. 363; Schmid, a.a.O., N. 1390, S. 636, sowie N. 1592, S. 726). <ref-law> verweist hinsichtlich Zuständigkeit und Verfahren auf die Regeln, die für die Wiederaufnahme gelten, und damit auf die Bestimmungen über die Revision nach <ref-law>. Zuständig ist insoweit das Berufungsgericht (<ref-law> i.V.m <ref-law>). Erachtet dieses die Voraussetzungen für die Bewilligung der Wiederaufnahme des ursprünglichen Verfahrens als gegeben, so hebt es nach <ref-law> den Entscheid in der Hauptsache auf und weist die Sache entweder an die von ihm bezeichnete Behörde zurück (Abs. 2 lit. a), was auch das erstinstanzliche Gericht sein kann, oder fällt selber einen neuen Entscheid (Abs. 2 lit. b).
2.4 Nach dem Gesagten ist der Auffassung des Beschwerdeführers insofern zuzustimmen, als der Entscheid über eine nachträgliche Anordnung einer Massnahme nach <ref-law> i.V.m. <ref-law> an sich in die Zuständigkeit des erstinstanzlichen Gerichts fällt. Vorliegend geht es allerdings nicht um einen Fall, bei dem sich die Zuständigkeit nach diesen Gesetzesbestimmungen richtet. Mit dem (Haupt-)Antrag der Vollzugsbehörde auf Prüfung der nachträglichen Anordnung einer Verwahrung wurde ein Revisionsverfahren nach <ref-law> eingeleitet, wodurch die Zuständigkeit der Vorinstanz als Berufungsgericht im Sinne von <ref-law> i.V.m. <ref-law> begründet wurde. Im Rahmen ihrer Entscheidfindung bejahte diese die Voraussetzungen für eine Verfahrenswiederaufnahme und ordnete eine Verwahrung über den Beschwerdeführer an. Auf Beschwerde hin hob das Bundesgericht diesen Entscheid auf und wies die Angelegenheit an die Vorinstanz zurück. Die bundesgerichtliche Rückweisung lässt die einmal begründete Zuständigkeit der Vorinstanz nicht entfallen. Ist die Vorinstanz als Berufungsgericht bei Vorliegen eines Revisionsgrunds zuständig, nachträglich eine Verwahrung im Sinne von <ref-law> anzuordnen, so muss sie unter den restriktiven Voraussetzungen für eine Verfahrenswiederaufnahme nachträglich auch die weniger einschneidende stationäre therapeutische Massnahme nach <ref-law> anordnen können, deren materiellrechtliche Gesetzesgrundlage sich aus <ref-law> ergibt. Von einem Instanzenverlust zum Nachteil des Beschwerdeführers kann vor diesem Hintergrund nicht gesprochen werden. Im Übrigen sind die im bundesgerichtlichen Rückweisungsentscheid enthaltenen Vorgaben für die Vorinstanz verbindlich. Sie belassen ihr keinen (nennenswerten) Spielraum. Auch unter diesem Aspekt erscheinen eine Rückweisung an und die Beurteilung durch die erste Instanz als nicht zwingend. Sie führte zu einer unnötigen formalistischen Verzögerung und wäre mit dem Beschleunigungsgebot im Strafverfahren nicht vereinbar. Die Vorinstanz erachtet sich aus diesen Gründen für die nachträgliche Anordnung der stationären therapeutischen Massnahme zu Recht als zuständig und konnte ohne Rechtsverletzung von einer Überweisung des Verfahrens an die erste Instanz absehen.
3. 3.1 Der Beschwerdeführer macht geltend, er sei einer Behandlung im Sinne von <ref-law> i.V.m. <ref-law> nicht zugänglich. Aus den Gutachten vom 24. September 2008 und 30. Juni 2010 sowie aus den mündlichen Ausführungen der Sachverständigen vor Vorinstanz ergebe sich, dass die Therapieaussichten äusserst gering seien und die gängigen Therapieverfahren nicht ausreichten, um seine Persönlichkeitsstörung zu behandeln. Eine Massnahme nach <ref-law> sei nicht zweckmässig (Beschwerde, S. 15 f.).
Überdies sei das Gutachten vom 24. September 2008 betreffend Diagnose und Gefährlichkeitsbeurteilung veraltet. Die Erfahrungen im Vollzug liessen den Schluss zu, dass er sich massgeblich entwickelt habe. Er habe fast zehn Jahre im Gefängnis verbracht. In dieser Zeit könne ein derart junger Mensch nachreifen und sich verändern. Zwischen August 2007 und Februar 2008 habe er an einer Therapie teilgenommen. Aus dem Vollzugsplan September 2009 gehe in Bezug auf das Rückfallrisiko hervor, dass er in der Therapie deliktzentriert gearbeitet und die nötigen Handlungskompetenzen und -alternativen erworben habe, um eine erneute Tatbegehung zu vermeiden (Beschwerde, S. 17 ff.).
3.2 Gemäss <ref-law> i.V.m <ref-law> kann das Gericht gegenüber einem psychisch schwer gestörten Täter nachträglich eine stationäre therapeutische Behandlung anordnen, wenn die Tat mit der psychischen Störung in Zusammenhang steht und zu erwarten ist, dadurch lasse sich der Gefahr weiterer mit seiner psychischen Störung in Zusammenhang stehender Taten begegnen. Es muss hinreichend wahrscheinlich erscheinen, dass sich durch die Behandlung die Gefahr weiterer Straftaten deutlich verringern lässt. Die bloss vage Möglichkeit einer Verringerung der Gefahr und die Erwartung einer lediglich minimalen Verringerung reichen nicht aus. Es ist indessen nicht eine hinreichende Wahrscheinlichkeit erforderlich, dass nach einer stationären Behandlung von fünf Jahren die Voraussetzungen für eine bedingte Entlassung aus der stationären Massnahme gemäss <ref-law> erfüllt sind (vgl. <ref-ruling> E. 3.4.1).
3.3 Das Bundesgericht erwog im Rückweisungsentscheid gestützt auf die Gutachten, dass der Beschwerdeführer psychisch schwer gestört ist, die begangenen Straftaten mit seiner Persönlichkeitsstörung zusammenhängen und er qualifiziert gefährlich ist (Urteil 6B_487/2011 vom 30. Januar 2012 E. 3.5 und 3.6). Er erfüllt insofern die Anordnungsvoraussetzungen nach <ref-law> ohne weiteres (Entscheid, S. 10).
3.4 Weiter führte das Bundesgericht aus, der Beschwerdeführer sei entgegen der Ansicht der Vorinstanz nicht unbehandelbar. Die Gutachter hätten einer Massnahme nach <ref-law> nicht jeglichen Erfolg abgesprochen. Sie hielten eine Therapie zwar für schwierig, nicht aber für unmöglich. Es könne eine Motivationsbasis erarbeitet und ein Veränderungswille geschaffen werden. Damit sei vorliegend zumindest von einer Motivierbarkeit des Beschwerdeführers auszugehen, welche in einer Anfangsphase im Rahmen einer stationären therapeutischen Behandlung nach <ref-law> genügen könne. Dass der Beschwerdeführer therapeutische Massnahmen nicht kategorisch ablehne, zeige sich daran, dass er im Strafvollzug von sich aus eine therapeutische Behandlung begonnen habe. Hinzu komme, dass der noch junge Beschwerdeführer noch nie einer rechtsgenüglichen therapeutischen Behandlung zugeführt worden sei. Ohne einen solchen Versuch liesse sich gestützt auf die Ausführungen der Gutachter nicht sagen, dass eine adäquate Behandlung innert absehbarer Zeit, d.h. in der Regel innert fünf Jahren, nicht zu einer das Rückfallrisiko erkennbar reduzierenden Entwicklung des Beschwerdeführers führe (Urteil 6B_487/2011 vom 30. Januar 2012 E. 3.7).
Das Bundesgericht bejahte damit die grundsätzliche Therapierbarkeit des Beschwerdeführers und schloss ernsthafte Aussichten auf einen Behandlungserfolg im Sinne von <ref-law> nicht aus. An diese Vorgaben ist die Vorinstanz gebunden (zur Bindungswirkung von bundesgerichtlichen Rückweisungsentscheiden <ref-ruling> E. 2 und E. 2.1 mit Hinweisen; Urteil 6B_206/2012 vom 5. Juli 2012 E. 1.21.), wovon diese zutreffend ausgeht (Entscheid, S. 10). Soweit der Beschwerdeführer vor Bundesgericht vorbringt, er sei einer Behandlung nicht zugänglich, die Erfolgsaussichten einer Therapie seien verschwindend klein und eine Massnahme nach <ref-law> nicht zweckmässig (Beschwerde, S. 15 f.), ist er auf die Erwägungen im bundesgerichtlichen Rückweisungsentscheid zu verweisen. Er setzt sich mit seinen Vorbringen überdies in Widerspruch zu seiner bisherigen Argumentation, wonach er therapierbar sei und eine stationäre Behandlung längerfristig Aussichten auf Erfolg zeitigen würde (vgl. Beschwerde vom 11. Juni 2011 im Verfahren 6B_487/2011, S. 42 Ziff. 37). Schliesslich verkennt er, dass in seinem Fall bei Therapieunfähigkeit nicht auf die Anordnung einer Massnahme überhaupt verzichtet, sondern er aufgrund seiner schweren psychischen Störung und qualifizierten Gefährlichkeit nach <ref-law> i.V.m. <ref-law> verwahrt worden wäre.
3.5 Unbegründet ist der Einwand der mangelnden Aktualität der gutachterlichen Beurteilungsgrundlagen. Das Gutachten vom 24. September 2008 spricht sich umfassend zu den psychischen Befunden, der Diagnose, der Rückfallgefährlichkeit bzw. Legalprognose und der Massnahmebedürftigkeit und -fähigkeit aus. Dieses Gutachten wurde durch das psychiatrische Gutachten vom 30. Juni 2010 ergänzt und durch die differenzierten mündlichen Ausführungen der Gutachterin anlässlich der Verhandlung vom 6. Mai 2011 u.a. zur Diagnose und zur Rückfallgefährlichkeit bestätigt. Inwiefern die gutachterliche Beurteilung aufgrund einer zwischenzeitlichen Entwicklung des Beschwerdeführers hinsichtlich Diagnose und Rückfallgefährlichkeit nicht mehr zutreffen sollte, ist nicht ersichtlich. Sein Einwand, er erbringe im Vollzug gute Arbeitsleistungen und verhalte sich klaglos (Beschwerde, S. 18 mit Verweis auf aktuellen Führungsbericht vom 5. Juli 2012), ist insofern nicht aussagekräftig. Nichts anderes gilt für den von ihm angeführten Umstand, er habe von August 2007 bis Februar 2008 eine Therapie besucht, deliktzentriert gearbeitet und Strategien erworben, um neue Tatbegehungen zu vermeiden (Beschwerde, S. 18 f.). Die Vorinstanz weist zutreffend darauf hin, dass die erwähnte therapeutische Behandlung sowohl vor der ersten als auch der ergänzenden Begutachtung stattgefunden und keine Änderung in Bezug auf die gutachterliche Beurteilung der Legalprognose bewirkt hat (Entscheid, S. 7). Die Ausführungen des Beschwerdeführers, mit welchen er seine Therapierbarkeit belegt, beschlagen im Übrigen nicht die Frage der Aktualität, sondern diejenige der Qualität und Vollständigkeit des Gutachtens. Darüber hat das Bundesgericht im Verfahren 6B_487/2011 bereits abschliessend befunden.
4.1 4.1.1 Der Beschwerdeführer macht geltend, sämtliche Straftaten vor dem Jahr 2007 verübt zu haben. Da <ref-law> erst am 1. Januar 2007 in Kraft getreten sei, könne diese Bestimmung auf ihn nicht angewendet werden, ohne den Grundsatz "nulla poena sine lege" und das Rückwirkungsverbot gemäss Art. 1 und 2 StGB sowie gemäss Art. 7 Abs. 1 EMRK und Art. 15 UNO-Pakt II zu verletzen. Er werde seine Strafe im Frühling 2013 vollständig verbüsst haben. Die nachträgliche Anordnung der stationären therapeutischen Massnahme lasse sich mit Art. 5 EMRK nicht vereinbaren. Sie laufe auf eine Doppelbestrafung gemäss Art. 4 des Zusatzprotokolls Nr. 7 zur EMRK und Art. 14 UNO Pakt II hinaus (Beschwerde, S. 12 ff.).
4.1.2 Nach Auffassung der Vorinstanz steht die nachträgliche Anordnung der stationären therapeutischen Massnahme im Einklang mit übergeordnetem Recht. Bereits in ihrem Urteil vom 6. Mai 2011 habe sie sich mit den Vorbringen des Beschwerdeführers ausführlich befasst. Ob das Rückwirkungsverbot und der Grundsatz "ne bis in idem" verletzt seien, beurteile sich bei der späteren Massnahmeanordnung nach <ref-law> nicht anders als bei der nachträglichen Verwahrung nach <ref-law> (Entscheid, S. 6 mit Verweis auf das Urteil vom 6. Mai 2011, S. 4 f.). Ziff. 2 der Schlussbestimmungen der Änderung des StGB vom 13. Dezember 2002 schliesse eine unzulässige Rückwirkung bzw. eine Verletzung des Grundsatzes "nulla poena sine lege" aus. Der Grundsatz "ne bis in idem" sei nicht verletzt, weil die nachträgliche Verwahrung gemäss <ref-law> als Wiederaufnahme eines Verfahrens zu Ungunsten des Betroffenen aufgrund neuer, bisher nicht berücksichtigter Tatsachen ausgestaltet worden sei.
4.2 Am 1. Januar 2007 sind der revidierte Allgemeine Teil des Strafgesetzbuches (Erstes Buch) und die revidierten Bestimmungen über die Einführung und Anwendung des Gesetzes (Drittes Buch) vom 13. Dezember 2002 bzw. vom 24. März 2006 in Kraft getreten. Im Rahmen der Revision wurde <ref-law> geschaffen. Mit dieser Bestimmung eröffnet das StGB die gesetzliche Möglichkeit, im Nachgang an eine (blosse) Strafe Massnahmen nach Art. 59 - 61 StGB (Abs. 1) oder die Verwahrung nach <ref-law> (Abs. 2) anzuordnen.
Gemäss <ref-law> wird nach dem Strafgesetzbuch beurteilt, wer nach dessen Inkrafttreten ein Verbrechen oder Vergehen begangen hat. Hat der Täter vor Inkrafttreten des Gesetzes ein Verbrechen oder Vergehen verübt, ist gemäss <ref-law> das neue Recht anwendbar, wenn es für den Täter das mildere ist.
Abweichend von dieser allgemeinen Bestimmung über den zeitlichen Geltungsbereich des Gesetzes enthält Ziff. 2 Abs. 1 der Schlussbestimmungen der Änderung vom 13. Dezember 2002 in Bezug auf das Massnahmenrecht eine spezielle Regelung. Danach sind die neuen Bestimmungen von Art. 56 - 65 auch auf diejenigen Täter anwendbar, die vor deren Inkrafttreten eine Tat begangen haben oder beurteilt worden sind. Die Bestimmung sieht somit die rückwirkende Anwendung des neuen Massnahmenrechts auch für bereits verurteilte Täter vor.
4.3 Die rückwirkende Anwendung des neuen Massnahmenrechts steht in einem Spannungsverhältnis zum Grundsatz "nulla poena sine lege" gemäss Art. 7 Abs. 1 EMRK und Art. 15 Abs. 1 des Internationalen Pakts über bürgerliche und politische Rechte (IPBPR; SR 0.103.2). Danach darf niemand wegen einer Handlung oder Unterlassung verurteilt werden, die zur Zeit ihrer Begehung nach innerstaatlichem oder internationalem Recht nicht strafbar war. Es darf auch keine höhere bzw. schwerere als die zur Zeit der Begehung angedrohte Strafe verhängt werden. Wird nach Begehung einer strafbaren Handlung durch Gesetz eine mildere Strafe eingeführt, so ist das mildere Gesetz anzuwenden (Art. 15 Abs. 1 Satz 3 UNO-Pakt II; vgl. <ref-ruling> E. 3.2). Diese Grundsätze ("nulla poena sine lege"; "lex mitior") sind auch im innerstaatlichen Recht (Art. 1 und 2 StGB) verankert. Aus ihnen ergibt sich das Verbot der Rückwirkung (vgl. Urteil 6B_103/2008 vom 9. Oktober 2008 E. 2.2.1).
4.4 Der Begriff der Strafe im Sinne von Art. 7 Abs. 1 EMRK ist autonom auszulegen. Er knüpft an eine strafrechtliche Verurteilung an. Der Begriff erfasst alle Verurteilungen, welche im Sinne von Art. 6 Abs. 1 EMRK gestützt auf eine gegen eine Person erhobene strafrechtliche Anklage ergehen. Von Bedeutung sind ferner ihre Qualifikation im nationalen Recht, das Verfahren, in dem sie verhängt und vollstreckt wird, sowie namentlich ihre Eingriffsschwere (<ref-ruling> E. 3.3. mit Hinweisen; s.a. Joachim Renzikowski, Das Elend mit der rückwirkend verlängerten und der nachträglich angeordneten Sicherungsverwahrung, in Zeitschrift für Internationale Strafrechtsdogmatik (ZIS) 6/2011, S. 531 ff., 533 ff, mit zahlreichen Hinweisen auf die EGMR-Rechtsprechung).
4.5 Das Bundesgericht lehnte es in seiner früheren, vor der Ratifikation der EMRK ergangenen Rechtsprechung ab, das Rückwirkungsverbot und damit - im Rahmen der Anwendung des StGB - die Frage der "lex mitior" auf sichernde oder erzieherische Massnahmen zu erstrecken (<ref-ruling> E. 1 a und b; 68 IV 36). Diese Rechtsprechung änderte es insofern, als es in <ref-ruling> entschied, das Rückwirkungsverbot gelte auch für die Verwahrung, da diese "mit dem Strafübel" grosse Ähnlichkeit aufweise und sich Strafe und Verwahrung im Vollzug nicht deutlich unterscheiden würden (BGE, a.a.O., E. 3.3.3).
4.6 Die Frage, ob das Rückwirkungsverbot auch für die nachträgliche Anordnung einer stationären therapeutischen Massnahme nach <ref-law> i.V.m. <ref-law> gilt, jedenfalls soweit es sich um eine Einweisung in eine geschlossene Einrichtung im Sinne von <ref-law> handelt, kann hier offen bleiben. Denn selbst wenn diese präventiv auf Behandlung und Sicherung ausgerichtete Massnahme im Sinne von Art. 7 Abs. 1 EMRK als Strafe einzuordnen wäre (siehe zum Charakter dieser Massnahme: Botschaft des Bundesrates zur Änderung des Schweizerischen Strafgesetzbuchs, vom 21. September 1998, BBl 1999 II 1979, 2075; Peter Albrecht, Die Verwahrung nach <ref-law> wirklich nur "ulitma ratio"?, in: AJP 9/2009, S. 1116 ff., S. 1122; Marianne Heer, in: Basler Kommentar, Strafrecht I, 2. Aufl., N. 14 ff. zu Art. 56 und N. 102 ff. zu <ref-law>; ähnlich Günter Stratenwerth, Schweizerisches Strafrecht, Strafen und Massnahmen, AT I, 2. Aufl., Bern 2006, § 8 N. 26 sowie § 9 N. 31 f.; Franz Riklin, Revision des Allgemeinen Teils des Strafgesetzbuches: Fragen des Übergangsrechts, in: AJP 12/2006, S. 1471 ff., S. 1478 sowie S. 1483), wird der Beschwerdeführer durch deren nachträgliche Anordnung nicht strenger bestraft als nach dem zur Zeit der Tatbegehung geltenden Recht.
4.6.1 Bereits die vor Inkrafttreten des revidierten allgemeinen Teils des Strafgesetzbuches geltende Strafprozessordnung des Kantons Basel-Stadt (StPO/BS) sah nämlich die Möglichkeit einer Urteilsrevision zu Lasten eines Betroffenen aufgrund von neuen Tatsachen und Beweismitteln vor. Danach war ein durch rechtskräftiges Urteil beendigtes Verfahren gemäss § 189 Abs. 1 lit. e aStPO/BS wieder aufzunehmen, wenn dem urteilenden Gericht nicht bekannte Tatsachen oder Beweismittel als geeignet erschienen, [...] eine wesentlich strengere Bestrafung einer verurteilten Person zu begründen. Bei gegebenen revisionsrechtlichen Voraussetzungen hätte mithin bereits gestützt auf das damals anwendbare kantonale Prozessrecht aufgrund von neuen, dem urteilenden Gericht unbekannten Tatsachen bzw. Beweismitteln auf das frühere Urteil zurückgekommen und eine deutlich strengere Sanktion ausgesprochen werden dürfen. Darunter fällt neben einer höheren Freiheitsstrafe auch - falls notwendig, geeignet und verhältnismässig - die nachträgliche Anordnung von Massnahmen unter Einschluss der Verwahrung im Sinne von Art. 43 aStGB. Dass die Voraussetzungen für die altrechtliche Einweisung in eine Heilanstalt vorgelegen haben, bejaht die Vorinstanz (Entscheid, S. 10). Der Beschwerdeführer äussert sich hierzu nicht.
4.6.2 Die Regelung gemäss § 189 Abs. 1 lit. e aStPO/BS entspricht derjenigen nach <ref-law> i.V.m. <ref-law>. Das Bundesgericht bejahte im Rückweisungsentscheid vom 30. Januar 2012 die Voraussetzungen zur Verfahrenswiederaufnahme zum Nachteil des Beschwerdeführers aufgrund von neuen Beweismitteln (Gutachten) bzw. neuen revisionsrelevanten Tatsachen. Dieser sei erstmals während des Vollzugs seiner Strafe am 24. September 2008 und (erneut) am 30. Juni 2010 psychiatrisch begutachtet worden. Die Gutachten sowie die Ausführungen der Sachverständigen anlässlich der damaligen vorinstanzlichen Verhandlung hätten ergeben, dass der Beschwerdeführer psychisch schwer gestört und im Sinne von <ref-law> qualifiziert gefährlich sei. Diese zum Zeitpunkt der Tatbegehungen und des Sachurteils bereits bestehenden tatsächlichen Umstände seien dem urteilenden Sachgericht nicht bekannt gewesen und hätten ihm auch nicht bekannt sein können, weil der Beschwerdeführer nie zuvor psychiatrisch begutachtet worden sei und hierzu - wegen der Nichterkennbarkeit der Störungen - auch kein Anlass bestanden habe (Urteil 6B_487/2011 E. 2, insbesondere E. 2.3).
4.6.3 Daran ist hier für die nachträgliche Massnahmeanordnung nach <ref-law> i.V.m. <ref-law> anzuknüpfen. War es nach altem (Prozess-)Recht zulässig und möglich, das Verfahren wegen neuer und erheblicher, dem Gericht nicht bekannter Tatsachen bzw. Beweismittel zu Lasten des Beschwerdeführers wieder aufzunehmen und diesen im Nachgang an die Strafe strenger zu bestrafen bzw. in eine Heilanstalt nach Art. 43 aStGB einzuweisen, erweist sich das alte Recht nicht milder, sondern mindestens ebenso streng wie das neue Recht, in dessen Rahmen die Vorinstanz den Revisionsgrund der neuen Tatsachen bzw. Beweismittel und die Voraussetzungen für die Anordnung einer stationären therapeutischen Massnahme ohne Rechtsverletzung als gegeben erachtete (vgl. Urteil 6B_487/2011 E. 2.3). Das Rückwirkungsverbot ist, soweit in dieser Konstellation überhaupt tangiert, nicht verletzt. Unter diesen Umständen kann offen bleiben, ob die nachträgliche Anordnung einer Massnahme nach <ref-law> i.V.m. <ref-law>, losgelöst von einer nach bisherigem kantonalen Recht zulässigen Wiederaufnahme des Verfahrens, mit dem völkerrechtlichen Rückwirkungsverbot vereinbar ist. Ebenso wenig muss beantwortet werden, ob Ziff. 2 der Schlussbestimmungen der Änderung des StGB vom 13. Dezember 2002 eine allfällig unzulässige Rückwirkung nach Art. 7 Abs. 1 EMRK und Art. 15 Abs. 1 UNO-Pakt II zu beseitigen vermöchte.
4.7 Die Neuanordnung einer stationären therapeutischen Massnahme im Nachgang an eine Strafe stellt einen Eingriff in die Rechtskraft des Urteils in der Hauptsache dar. Gemäss konstanter Rechtsprechung zur späteren Abänderung von Massnahmen (vgl. <ref-ruling>) ist daher auch hier zu prüfen, ob der nachträgliche Wechsel von einer Strafe zu einer Massnahme konventionskonform ist.
4.7.1 Nach Art. 5 Abs. 1 lit. a EMRK muss eine Sanktion auf einer gerichtlichen Verurteilung beruhen (EGMR, Van Droogenbroeck vs. Belgien, Urteil vom 24.6.1982, § 35; in: Europäische Grundrechte-Zeitschrift (EuGRZ) 1984, S. 7 f.). Die spätere Anordnung oder Anpassung einer 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 mithin einer zeitlichen und inhaltlichen Verknüpfung zwischen Verurteilung und (erneuter) Freiheitsentziehung. Erforderlich ist, dass das Ausgangsurteil den späteren Freiheitsentzug noch "trägt" bzw. sich die Freiheitsentziehung aus der ursprünglichen Verurteilung gerade ergibt (<ref-ruling> E. 3.3. mit Hinweisen auf Literatur und Rechtsprechung; s.a. Urteil 6B_135/2012 E. 1.3.).
4.7.2 Mit der konkreten Wiederaufnahme des Verfahrens zu Ungunsten des Beschwerdeführers wird auf das ursprüngliche Urteil in der Sache zurückgekommen und die nachträgliche Anordnung der Massnahme nach <ref-law> i.V.m. <ref-law> daran angebunden (vgl. BBl 2005, S. 4689 ff., 4714; s.a. HeeR, a.a.O., N. 15 und 30 zu Art. 65; Riklin, a.a.O., S. 1483). Das ursprüngliche Urteil in der Sache bildet mithin den Rechtsgrund (und nicht nur den Anlass) für die spätere Freiheitsentziehung, weil die Gründe für die erneute Inhaftierung nicht erst nachträglich während des Strafvollzugs entstanden, sondern bereits zum Zeitpunkt der Tatbegehung und der ursprünglichen Verurteilung vorlagen. Mit andern Worten hätte das urteilende Sachgericht eine solche Massnahme angeordnet, wenn es um die tatsächlichen Umstände des Geisteszustands des Beschwerdeführers und seiner daraus resultierenden Gefährlichkeit gewusst hätte. Damit ist die vom EGMR geforderte "sufficient causal connection" im Sinne von Art. 5 Abs. 1 lit. a EMRK zwischen dem Ausgangsurteil und der nachträglichen Anordnung einer Massnahme gegeben.
4.8 Schliesslich ist auch der Grundsatz "ne bis in idem" nicht verletzt.
Nach dieser Maxime darf ein Beschuldigter nicht wegen derselben Tat mehrmals verfolgt und bestraft werden und steht einem zweiten Strafverfahren die materielle Rechtskraft des in derselben Sache ergangenen ersten Urteils entgegen (vgl. Art. 4 Abs. 1 des Protokolls Nr. 7 zur EMRK vom 22. November 1984 [SR 0.101.07]; Art. 14 Abs. 7 IPB PR [SR 0.103.2]; <ref-ruling> E. 5; <ref-ruling> E. 2b; ). Die Anwendung des Prinzips "ne bis in idem" setzt unter anderem voraus, dass dem Richter im ersten Verfahren die Möglichkeit zugestanden haben muss, den Sachverhalt unter allen tatbestandsmässigen Punkten zu würdigen (<ref-ruling> E. 3.3; <ref-ruling> E. 3c mit Hinweisen).
Art. 4 Abs. 2 des Protokolls Nr. 7 zur EMRK lässt weitgehende Ausnahmen vom Grundsatz "ne bis in idem" zu. Die Wiederaufnahme des Verfahrens zu Ungunsten des Betroffenen ist danach möglich, wenn neue oder neu bekannt gewordene Tatsachen vorliegen oder das vorausgegangene Verfahren schwere, den Ausgang des Verfahrens berührende Mängel aufweist. Das gilt nach der Lehre auch für bereits verurteilte Täter, wenn der Mangel des Verfahrens oder die Unbekanntheit von Tatsachen eine (erheblich) schwerere Bestrafung verhindert hatte (Riklin, a.a.O., S. 1477 und 1483 mit weiteren Hinweisen; Stefan Trechsel, Das verflixte Siebente, Bemerkungen zum 7. Zusatzprotokoll zur EMRK, in: Festschrift für Felix Ermacora, 1988, S. 207; s.a. Grabenwarter/Pabel, Europäische Menschenrechtskonvention, 2012, 5. Aufl., S. 476 N. 151). Mit der Verfahrenswiederaufnahme aufgrund von neuen revisionserheblichen Tatsachen bzw. Beweismitteln ist der Bezug zum ursprünglichen Urteil in der Hauptsache gegeben und werden die Anlasstaten nicht doppelt sanktioniert. Es wird (vielmehr) an die zum Zeitpunkt der Tatbegehung und des ursprünglichen Urteils bereits vorgelegene (aber übersehene) schwere psychische Störung des Beschwerdeführers und dessen qualifizierte Gefährlichkeit angeknüpft.
In Art. 14 Abs. 7 UNO-Pakt II ist die Wiederaufnahme des Verfahrens zum Nachteil des Täters nicht vorgesehen. Die Schweiz hat keinen Vorbehalt angebracht. Bei Vorliegen aussergewöhnlicher Umstände begründet die Verfahrenswiederaufnahme (trotz Fehlens eines Vorbehalts) jedoch auch in diesem Zusammenhang keine Verletzung des Grundsatzes "ne bis in idem" (Riklin, a.a.O., S. 1477, Fn 42; Heer, a.a.O., N. 31 zu Art. 65 mit Hinweisen; Manfred Nowak, CCPR Commentary, U.N. Covenant on Civil and Political Rights, 2005, 2. Aufl., Art. 14 N. 100 sowie S. 1099 ff., S. 1102). Von solch aussergewöhnlichen Umständen, die eine Verfahrenswiederaufnahme erlauben und mit dem Grundsatz "ne bis in idem" nicht im Konflikt stehen, kann hier angesichts der bislang unbekannten, tatsächlichen Umstände betreffend den Geisteszustand des Beschwerdeführers und seiner sich daraus ergebenden qualifizierten Gefährlichkeit ausgegangen werden.
4.9 Die nachträgliche Anordnung einer stationären therapeutischen Massnahme erweist sich insgesamt als konventions- und bundesrechtskonform.
5. Die Beschwerde ist abzuweisen. Das Gesuch um unentgeltliche Rechtspflege ist gutzuheissen, da die Voraussetzungen erfüllt sind. Es sind keine Kosten zu erheben. Die Rechtsvertreterin des Beschwerdeführers ist aus der Bundesgerichtskasse zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
3. Es werden keine Gerichtskosten erhoben.
4. Die Rechtsvertreterin des Beschwerdeführers, Rechtsanwältin Sandra Sutter-Jeker, wird aus der Bundesgerichtskasse mit Fr. 3'000.-- entschädigt.
5. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 28. Mai 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill