Sachverhalt:
A. Das Appellationsgericht des Kantons Basel-Stadt sprach den am 10. März 1982 geborenen X._ am 12. Januar 2007 zweitinstanzlich schuldig des qualifizierten Raubes, der Gefährdung des Lebens, der 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. Es verurteilte X._ zu einer Freiheitsstrafe von 8 Jahren, unter Anrechnung der bis anhin verbüssten Haft. 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). Es beurteilte ihn als gefährlichen Gewalttäter.
Die gegen diesen Entscheid erhobene Beschwerde von X._ (Schuldpunkt, Strafzumessung) wies das Bundesgericht am 12. Mai 2007 ab (Verfahren 6B_48/2007).
B. X._ verbüsst seine Strafe seit dem 19. Juli 2005 in der Strafanstalt A._. Auf sein Gesuch um Vollzugslockerungen vom 4. Juli 2007 hin stufte ihn die Interkantonale Fachkommission zur Beurteilung der Gemeingefährlichkeit von Straftätern der Kantone Solothurn, Basel-Landschaft und Basel-Stadt (IFKGS) am 29. Oktober 2007 als gemeingefährlich ein. Hinweise auf eine Krankheit oder eine Persönlichkeitsstörung schloss die IFKGS aus.
Die Abteilung Freiheitsentzug und Soziale Dienste (heute Abteilung Strafvollzug) des Justizdepartements (heute 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 dem Gutachten vom 24. September 2008 leidet X._ an einer schwer zu behandelnden paranoiden und narzisstischen Persönlichkeitsstörung, welche schon im Tatzeitpunkt bestand. Die von ihm ausgehende Rückfallgefahr wird als erheblich eingestuft. Es seien namentlich Raubstraftaten mit hoher Wahrscheinlichkeit zu erwarten, wobei es zu Gewalttaten gegenüber den Opfern kommen könne, wenn sich diese wehrten. Die Legalprognose sei sehr ungünstig. Am 10. November 2008 stufte die IFKGS X._ erneut als gemeingefährlich ein. Sie empfahl, die Anordnung einer vollzugsbegleitenden ambulanten Massnahme abklären zu lassen.
Am 30. Dezember 2008 stellte die Abteilung Strafvollzug des JSD dem Appellationsgericht den Antrag auf Prüfung der nachträglichen Anordnung einer vollzugsbegleitenden psychotherapeutischen ambulanten Behandlung. Mit Entscheid vom 4. Dezember 2009 wies das Appellationsgericht diesen Antrag mangels Gesetzesgrundlage ab. Es warf aber die Frage auf, ob nicht allenfalls eine stationäre Behandlung im Sinne von Art. 65 Abs. 1 StGB in Betracht zu ziehen wäre, und regte für diesen Fall die Einholung eines Ergänzungsgutachtens an.
Die Abteilung Strafvollzug des JSD holte beim FPD der Universität Bern ein solches Ergänzungsgutachten ein. Es datiert vom 30. Juni 2010. Namentlich gestützt darauf beantragte die Abteilung Strafvollzug des JSD am 7. Juli 2010 die Prüfung der nachträglichen Anordnung einer Verwahrung gemäss Art. 65 Abs. 2 StGB, wobei auch die Möglichkeit der nachträglichen Anordnung einer stationären Massnahme nach Abs. 1 der genannten Gesetzesbestimmung nicht ausgeschlossen werden sollte.
Mit Entscheid vom 6. Mai 2011 ordnete das Appellationsgericht des Kantons Basel-Stadt über X._ nachträglich eine Verwahrung im Sinne von Art. 65 Abs. 2 StGB an.
C. X._ erhebt Beschwerde in Strafsachen. Er beantragt, es sei das angefochtene Urteil vom 6. Mai 2011 aufzuheben und festzustellen, dass die Voraussetzungen für die nachträgliche Anordnung der Verwahrung nach Art. 65 Abs. 2 StGB nicht gegeben seien. Eventualiter sei das angefochtene Urteil vom 6. Mai 2011 aufzuheben und die Sache im Sinne der Erwägungen an die Vorinstanz zur Neubeurteilung zurückzuweisen. Gleichzeitig ersucht X._ um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
D. Die Abteilung Strafvollzug des JSD teilt mit Eingabe vom 23. November 2011 mit, im vorliegenden Verfahren nicht Partei zu sein. Sie sieht deshalb von einer Vernehmlassung ab. Die Staatsanwaltschaft des Kantons Basel-Stadt verzichtet am 5. Dezember 2011 auf eine Stellungnahme. Das Appellationsgericht des Kantons Basel-Stadt beantragt mit Eingabe vom 9. Dezember 2011 die kostenfällige Abweisung der Beschwerde. Mit Eingabe vom 6. Januar 2012 hält der Vertreter von X._ an seinen bisherigen Standpunkten fest.
Erwägungen:
1. 1.1 Der Beschwerdeführer erhebt eine Vielzahl von Verfahrensrügen. Er macht zunächst geltend, die am vorinstanzlichen Entscheid mitwirkenden Richter, die psychiatrische Sachverständige Prof. Dr. B._ sowie der Vorsteher der IFKGS seien vorbefasst und voreingenommen (Beschwerde, S. 11 ff., 21 ff.).
1.2 1.2.1 Gemäss Art. 30 Abs. 1 BV und Art. 6 Ziff. 1 EMRK hat jede Person Anspruch darauf, dass ihre Sache von einem unparteiischen, unvoreingenommenen und unbefangenen Richter entschieden wird (BGE 136 I 207 E. 3.1). Nach der Rechtsprechung des Bundesgerichts wird diese Verfahrensgarantie sinngemäss auch auf das Erfordernis der Unabhängigkeit und Unparteilichkeit von Sachverständigen übertragen (BGE 132 V 93 E. 7.1; 125 II 541 E. 4a mit Hinweisen; Urteil 9C_243/2010 vom 28. Juni 2011 E. 2.1.3; ausführlich auch das Urteil 6B_258/2011 vom 22. August 2011).
Ablehnungsgründe gegen einen oder mehrere Richter oder gegen sachverständige Personen sind nach Treu und Glauben ohne Verzug geltend zu machen. Wer von einem Ablehnungsgrund Kenntnis erhält und nicht unverzüglich ein Begehren um Ablehnung stellt, sondern sich auf den Prozess einlässt, verwirkt den Anspruch gemäss Art. 30 Abs. 1 BV (BGE 128 V 82 E. 2b; 124 I 121 E. 2; 119 Ia 221 E. 5a). Die Kantone dürfen verlangen, dass Ablehnungsbegehren frist- und formgerecht erhoben werden (BGE 124 I 121 E. 2 S. 123).
1.2.2 Bei den Verfahren betreffend nachträgliche Anordnung von Massnahmen geht es um die Abänderung oder Ergänzung der Sanktionsfolgen von rechtskräftigen Strafurteilen. Es handelt sich um sogenannte Nachverfahren (vgl. ANDREAS DONATSCH ET AL., Kommentar zur Schweizerischen Strafprozessordnung (StPO), Zürich 2010, Art. 363 Rz. 1 ff.).
1.2.3 Der anwaltlich vertretene Beschwerdeführer stellte im Verfahren betreffend nachträgliche Anordnung einer ambulanten Massnahme den Antrag, das im Nachverfahren urteilende Gericht sei ausschliesslich mit Richtern und Richterinnen zu besetzen, die nicht bereits am Strafverfahren teilgenommen hätten. Das Appellationsgericht wies dieses Ablehnungsbegehren mit Entscheid vom 2. April 2009 ab, soweit es darauf eintrat. Dieser Entscheid erwuchs unangefochten in Rechtskraft.
1.2.4 Im Verfahren betreffend nachträgliche Anordnung der Verwahrung brachte der Beschwerdeführer den Einwand der Vorbefassung und der Befangenheit nicht mehr vor. Es wäre ihm jedoch zumutbar und möglich gewesen, spätestens anlässlich der Verhandlung vor Vorinstanz am 6. Mai 2011 ein Ablehnungsbegehren zu stellen, als er realisierte, dass am vorliegenden Verfahren erneut dieselben Richter mitwirkten wie bereits teilweise im ursprünglichen Strafverfahren und im Nachverfahren betreffend Gesuch um nachträgliche Anordnung einer vollzugsbegleitenden ambulanten Massnahme. Das tat er nicht. Stattdessen liess er sich trotz Kenntnis des von ihm behaupteten Ablehnungsgrunds stillschweigend und vorbehaltlos auf das Verfahren vor Vorinstanz ein. Es verstösst gegen Treu und Glauben, wenn eine Partei einen angeblichen Mangel nicht unverzüglich vorbringt, sondern zuwartet, um ihn allenfalls erst im Anschluss an ein für sie ungünstiges Urteil des betreffenden Gerichts geltend zu machen (BGE 132 II 485 E. 4.3 mit Hinweisen). Indem der Beschwerdeführer mit seiner Rüge bis vor Bundesgericht zuwartete, muss diese als verspätet und damit als verwirkt betrachtet werden. Darauf ist nicht einzutreten.
1.2.5 Wegen Verspätung grundsätzlich nicht einzutreten ist auf die Befangenheitsrügen gegen die psychiatrische Sachverständige Prof. Dr. B._ und den Vorsteher der IFKGS wegen Vorbefassung und Ämterkumulation (Beschwerde, S. 21 f.). Die Rügen sind in Bezug auf die psychiatrische Sachverständige im Hinblick auf Art. 56 Abs. 4 StGB trotzdem zu prüfen. Sie gehen an der Sache vorbei. Besondere Umstände, welche den Beizug einer neuen sachverständigen Person als notwendig hätten erscheinen lassen können, liegen nicht vor. Insbesondere ergeben sich weder aus der Art der Begutachtung noch aus dem Gutachten selber Anzeichen für eine Voreingenommenheit der Expertin. Der Umstand, dass sich Prof. Dr. B._ als Sachverständige bereits im Gutachten vom 24. September 2008 mit dem Beschwerdeführer befasste, lässt sie im Hinblick auf die Erstellung des Ergänzungsgutachtens vom 30. Juni 2010 nicht als befangen erscheinen (vgl. BGE 132 V 93 E. 7.1; Urteile 6B_92/2010 vom 30. März 2010 E. 3.3. und 9C_893/2009 vom 22. Dezember 2009). Im Übrigen war sie auch nicht Mitglied der IFKGS und an deren Gemeingefährlichkeitsbeurteilung nicht beteiligt (vgl. kantonale Akten, Beurteilungen der IFKGS vom 20. September 2007 und 10. November 2008).
1.3 Der Beschwerdeführer behauptet weiter, er sei nicht durch ein ordentlich besetztes Gericht im Sinne von Art. 30 Abs. 1 BV und Art. 6 Ziff. 1 EMRK angehört worden, weil ein Richter während des Plädoyers für einige Sekunden eingeschlafen sei (Beschwerde, S. 13). Wiewohl zumutbar und möglich, beanstandete er während der Verhandlung ein solches Verhalten nicht (kantonale Akten, Verhandlungsprotokoll vom 6. Mai 2011). Die Frage des Eintretens kann offen gelassen werden, da das Vorbringen offensichtlich nicht geeignet ist, eine Verfassungs- oder Konventionsverletzung zu begründen. Ein Sekundenschlaf - so wie vom Beschwerdeführer geschildert - beeinträchtigt die Fähigkeit nicht, einer Verhandlung in ihrer Gänze bewusst und aufmerksam zu folgen bzw. deren wesentlichen Teil aufzunehmen. Das gilt umso mehr, als den teilnehmenden Richtern die Stellungnahme des Anwalts des Beschwerdeführers zum Antrag auf nachträgliche Anordnung der Verwahrung in schriftlicher Form vorlag. Spekulativ ist das weitere Vorbringen in der Beschwerde, die fragliche Richterperson sei während der Verhandlung möglicherweise mehrmals in einen Sekundenschlaf gefallen. Darauf ist nicht einzugehen.
1.4 Der Beschwerdeführer rügt eine Verletzung des Anspruchs auf rechtliches Gehör im Sinne von Art. 29 Abs. 2 BV. Weder vor noch nach den Sitzungen der IFKGS vom 20. September 2007 und 10. November 2008 habe er sich zur Frage seiner Gemeingefährlichkeit äussern können (Beschwerde, S. 13 f.). Diesen Einwand erhob der Beschwerdeführer im Verfahren vor Vorinstanz nicht. Sie befasst sich im angefochtenen Entscheid denn auch nicht damit. Dass sie dies zu Unrecht nicht tut, macht der Beschwerdeführer vor Bundesgericht nicht geltend. Mangels Erschöpfung des kantonalen Instanzenzugs fehlt es insoweit an einem zulässigen Anfechtungsobjekt nach Art. 80 Abs. 1 BGG. Aus dem gleichen Grund ist auf den Einwand des Beschwerdeführers nicht einzutreten, er sei bei der Begutachtung durch den FPD der Universität Bern im Zuge der psychiatrischen und körperlichen Untersuchungen vom 8. Juli und 12. August 2008 nicht über seine Rechte informiert worden (Beschwerde S. 13, 28). Aus einem Hinweis im Gutachten vom 24. September 2008 (S. 17) ergibt sich im Übrigen, dass der Beschwerdeführer vor den körperlichen und psychiatrischen Untersuchungen ausdrücklich über seine Rechte auf Nichteinlassung aufgeklärt wurde. Dasselbe geht aus dem Ergänzungsgutachten vom 30. Juni 2010 (S. 7) hervor. Eine Gehörsverletzung ist unter diesen Umständen nicht erkennbar.
1.5 Zusammenfassend sind die Verfahrensrügen abzuweisen, soweit darauf einzutreten ist.
2. Der Beschwerdeführer wehrt sich gegen die Anordnung der nachträglichen Verwahrung. Er rügt eine Verletzung von Art. 65 Abs. 2 StGB. Die festgestellten psychischen Störungen seien den Sachgerichten bereits im damaligen Zeitpunkt in den Grundzügen im Sinne von Auffälligkeiten bzw. Charaktereigenschaften bekannt gewesen Es lägen mithin keine neuen Tatsachen vor, die dem Sachgericht im Zeitpunkt der Verurteilung nicht bekannt gewesen seien bzw. nicht bekannt gewesen sein konnten (Beschwerde, S. 18 ff. und 35 f.).
2.1 Gemäss Art. 65 Abs. 2 StGB kann das Gericht die Verwahrung nachträglich anordnen, wenn sich bei einem Verurteilten während des Vollzugs der Freiheitsstrafe aufgrund neuer Tatsachen oder Beweismittel ergibt, dass die Voraussetzungen der Verwahrung gegeben sind und im Zeitpunkt der Verurteilung bereits bestanden haben, ohne dass das Gericht davon Kenntnis haben konnte.
Mit Art. 65 Abs. 2 StGB besteht nach geltendem Recht die prozessuale Möglichkeit, einen rechtskräftig beurteilten Fall wieder aufzunehmen, und zwar insofern, als im Nachgang zur Ausfällung einer Freiheitsstrafe eine Verwahrung geprüft und allenfalls angeordnet werden kann. Die "nachträgliche Verwahrung" ist eine Revision zu Ungunsten des Verurteilten (BGE 137 IV 59 E. 5). Sie ist möglich, sofern sich während des Strafvollzugs aufgrund von neuen Tatsachen oder Beweismitteln ergibt, dass die Voraussetzungen der Verwahrung schon im Verurteilungszeitpunkt vorgelegen haben, diese dem Gericht aber nicht bekannt sein konnten. Der Anwendungsbereich von Art. 65 Abs. 2 StGB zielt auf die seltenen Fälle, in denen die an sich zulässige Anordnung einer Verwahrung im Strafurteil unterblieben ist und sich der Verurteilte während des Strafvollzugs als hochgefährlich erweist (siehe Botschaft BBl 2005, S. 4714; MARIANNE HEER, Basler Kommentar Strafrecht I, 2. Aufl., Basel 2007, Art. 65 N. 20 ff., DIES., Nachträgliche Verwahrung - ein gesetzgeberischer Irrläufer, AJP 2007, S. 1031 ff., 1033; FELIX BOMMER, Nachträgliche Verwahrung als Revision zulasten des Verurteilten, Zur Revisibilität von Prognoseentscheidungen, in Festschrift für Franz Riklin, Basel 2007, S. 55 ff., S. 58 und 60; zum Zeitpunkt der Gesuchseinreichung FRANZ RIKLIN, Strafen und Massnahmen im Überblick, in: Die Revision des Strafgesetzbuches, Allgemeiner Teil, Zürich 2006, S. 73 ff., 98; DERS., Revision des Allgemeinen Teils des Strafgesetzbuches: Fragen des Übergangsrechts, in AJP 2006, S. 1471 ff., S. 1481/2).
2.2 Die Revision im Sinne von Art. 65 Abs. 2 StGB ist an vier Voraussetzungen geknüpft:
2.2.1 Die Revision zu Ungunsten des Verurteilten muss auf Tatsachen oder Beweismitteln beruhen. Unter Tatsachen sind Umstände zu verstehen, die im Rahmen des dem Urteil zugrunde liegenden Sachverhalts von Bedeutung sind. Mit Beweismitteln wird der Nachweis von Tatsachen erbracht. Eine Meinung, eine persönliche Würdigung oder eine neue Rechtsauffassung vermögen die Revision nicht zu rechtfertigen (BGE 137 IV 59 E. 5.1.1).
2.2.2 Die Tatsachen oder Beweismittel, welche die Feststellung erlauben, dass die Voraussetzungen für eine Verwahrung erfüllt sind, müssen neu sein. Revisionsrechtlich sind Tatsachen oder Beweismittel neu, wenn sie dem früher urteilenden Gericht nicht vorgelegen haben, auch nicht als Hypothesen (siehe die bundesgerichtliche Rechtsprechung zu Art. 397 aStGB und Art. 385 StGB: BGE 130 IV 72 E. 1; vgl. auch BGE 116 IV 353 E. 3a; Urteil 6B_539/2008 vom 8. Oktober 2008 E. 1.2). Im Unterschied zu Art. 385 StGB resp. Art. 397 aStGB ist es bei Art. 65 Abs. 2 StGB von Bedeutung, weshalb das Gericht von der Tatsache oder dem Beweismittel keine Kenntnis hatte. Gemäss Art. 385 StGB resp. Art. 397 aStGB haben die Kantone die Wiederaufnahme des Verfahrens zu Gunsten des Verurteilten wegen Tatsachen oder Beweismittel zu gestatten, die dem Gericht zur Zeit des früheren Verfahrens nicht bekannt waren. Art. 385 StGB resp. Art. 397 aStGB knüpft alleine an das tatsächliche Fehlen der Kenntnis an. Demgegenüber kommt die nachträgliche Verwahrung nach Art. 65 Abs. 2 StGB - restriktiver - ausschliesslich in Betracht aufgrund von Tatsachen oder Beweismitteln, die im Zeitpunkt der Verurteilung bereits bestanden haben, ohne dass das Gericht davon Kenntnis haben konnte. Als neu im Sinne der genannten Bestimmung gelten daher gemäss Art. 65 Abs. 2 StGB nur Tatsachen, die dem Gericht nicht bekannt waren und ihm nicht bekannt sein konnten, im Urteilszeitpunkt aber schon bestanden haben. Es geht um Fakten, die für das Gericht objektiv unmöglich erkennbar waren (BGE 137 IV 59 E. 5.1.2 mit Hinweisen, eingehend MARIANNE HEER, Basler Kommentar, Schweizerische Strafprozessordnung, 2011, Rz. 40 zu Art. 410 StPO; siehe auch BOMMER, a.a.O., S. 66).
Ein neues Gutachten kann Anlass zur Wiederaufnahme geben, wenn es neue Tatsachen nachweist oder darzutun vermag, dass die tatsächlichen Annahmen im früheren Urteil ungenau oder falsch waren. Dabei kann es sich auch um ein Privatgutachten handeln. Ein neues Gutachten, das lediglich eine von einem früheren Gutachten abweichende Meinung vertritt oder zu einer andern Würdigung gelangt, stellt nicht bereits einen Revisionsgrund dar. Es muss vielmehr mit überlegenen Gründen vom ersten Gutachten abweichen und klare Fehler des früheren Gutachtens aufzeigen, die geeignet sind, die Beweisgrundlage des ersten Urteils zu erschüttern (Urteil 6P.93/2004 vom 15. November 2004 E. 4; 6S.452/ 2004 vom 1. Oktober 2005 E. 2.2; 6B_539/2008 vom 8. Oktober 2008 E. 1.3). Ein Gutachten wird auch als neues Beweismittel betrachtet, wenn es sich auf neue Erkenntnisse stützt oder eine andere (überlegene) Methode anwendet (BGE 137 IV 59 E. 5.1.2).
2.2.3 Die Voraussetzungen für die Verwahrung müssen schon im Zeitpunkt der Urteilsfällung erfüllt gewesen sein. Es kann nicht Aufgabe des Gerichts im Verfahren um Wiederaufnahme sein, ein rechtskräftiges Urteil einem seither veränderten Sachverhalt anzupassen. Es geht vielmehr lediglich um die Korrektur eines Fehlers im früheren Verfahren. Entwicklungen des Täters im Verlaufe des Vollzugs (beispielsweise Verweigerung der Therapie, Aggressivität sowie Drohungen mit künftigen Straftaten) können revisionsrechtlich nicht massgebend sein (BGE 137 IV 59 E. 5.1.3).
2.2.4 Die neu angerufenen Tatsachen und Beweismittel müssen erheblich sein (BGE 122 IV 66 E. 2) und für sich alleine oder zusammen mit den andern Fakten in ihrer Gesamtheit eine Verwahrung begründen. Die dem Urteil zugrunde liegenden Feststellungen müssen so erschüttert werden, dass aufgrund des veränderten Sachverhalts eine Verwahrung wahrscheinlich erscheint (BGE 137 IV 59 E. 5.1.4).
2.3 Die relevanten psychiatrischen Befunde mit der Diagnose einer paranoiden und narzisstischen Persönlichkeitsstörung (ICD-10 F60.0; ICD-10 F60.80) sind erst mit den sachverständigen Begutachtungen vom 24. September 2008 und 30. Juni 2010 festgestellt worden. Die psychischen Störungen bestanden gemäss den Gutachten bereits zur Zeit der Taten. Sie waren den kantonalen Gerichtsinstanzen im Erkenntnisverfahren nicht bekannt und konnten ihnen nicht bekannt sein. Der Beschwerdeführer wurde zuvor nie begutachtet. Noch in der Beurteilung der IFKGS vom 29. Oktober 2007 wurde ausgeführt, dass keinerlei Hinweise bestünden, welche den Schluss auf eine Krankheit oder psychische Störung des Beschwerdeführers zuliessen. Anlässlich der Verhandlung vor Vorinstanz am 6. Mai 2011 wies die psychiatrische Sachverständige Prof. Dr. B._ darauf hin, die psychiatrischen Befunde bzw. Störungen beim Beschwerdeführer seien wahrscheinlich deshalb nicht erkannt worden, weil sich keine Fachperson mit ihm auseinandergesetzt habe. Menschen mit Persönlichkeitsstörungen wirkten für den Normalbetrachter oft unauffällig (mündliche Gutachtensergänzung, Verhandlungsprotokoll vom 6. Mai 2011, S. 3; Gutachten vom 24. September 2008, S. 41). Damit ergeben erst die Gutachten vom 24. September 2008 und 30. Juni 2010 unter Einschluss der mündlichen Ausführungen der Gutachterin das Vorliegen der Persönlichkeitsstörungen. Vor diesem Hintergrund kann auch nicht gesagt werden, die Nichteinholung eines Gutachtens im Erkenntnisverfahren beruhe auf einer Nachlässigkeit bzw. einem Versäumnis des damals urteilenden Gerichts. Dieses hatte - wie sich aus der nachvollziehbaren Erklärung der Gutachterin zur Nichterkennbarkeit der Störungen bzw. ihrer Befundtatsachen ergibt - keinen Anlass, eine Begutachtung anzuordnen. Vor diesem Hintergrund bejahte die Vorinstanz das Vorliegen neuer Beweismittel und neuer revisionsrechtlich relevanter Tatsachen (im Sinne eines gutachterlich verifizierten relevanten psychiatrischen Befunds) zu Recht (vgl. HEER, Basler Kommentar Strafrecht I, 2. Aufl., Basel 2007, Art. 65 N. 63; s.a. HANS WALDER, Die Wiederaufnahme des Verfahrens in Strafsachen nach Art. 397 StGB, insbesondere auf Grund eines neuen Gutachtens, in: Berner Festgabe zum Schweizerischen Juristentag 1979, Bern 1979, S. 346).
Damit bleibt darüber zu befinden, ob die Verwahrungsvoraussetzungen sowohl heute gegeben sind als auch bereits im damaligen Urteilszeitpunkt vorlagen.
3. Der Beschwerdeführer beging sämtliche Delikte vor Inkrafttreten des revidierten Massnahmerechts des StGB am 1. Januar 2007. Die nachträgliche Anordnung der Verwahrung nach Art. 65 Abs. 2 StGB setzt voraus, dass nicht nur die Voraussetzungen nach Art. 64 StGB im Revisionszeitpunkt erfüllt sind, sondern dass die Verwahrung auch nach Art. 42 oder Art. 43 Ziff. 1 Abs. 2 aStGB möglich gewesen wäre.
3. Der Beschwerdeführer beging sämtliche Delikte vor Inkrafttreten des revidierten Massnahmerechts des StGB am 1. Januar 2007. Die nachträgliche Anordnung der Verwahrung nach Art. 65 Abs. 2 StGB setzt voraus, dass nicht nur die Voraussetzungen nach Art. 64 StGB im Revisionszeitpunkt erfüllt sind, sondern dass die Verwahrung auch nach Art. 42 oder Art. 43 Ziff. 1 Abs. 2 aStGB möglich gewesen wäre.
3.1 3.1.1 Beim Entscheid über die nachträgliche Anordnung einer Verwahrung hat sich das Gericht auf eine sachverständige Begutachtung im Sinne von Art. 56 Abs. 3 StGB zu stützen. Das Gutachten muss sich zur Notwendigkeit und den Erfolgsaussichten einer Behandlung des Täters, Art und Wahrscheinlichkeit weiterer möglicher Straftaten und zu den Möglichkeiten des Vollzugs der Massnahme äussern (Art. 56 Abs. 3 lit. a, b und c StGB). Hat der Täter eine Anlasstat gemäss Art. 64 Abs. 1 StGB begangen, ist die Begutachtung durch einen Sachverständigen vorzunehmen, der den Täter weder behandelt noch in anderer Weise betreut hat (Art. 56 Abs. 4 StGB). Gemäss Art. 43 Ziff. 1 Abs. 3 aStGB trifft der Richter seinen Entscheid auf Grund von Gutachten über den körperlichen und geistigen Zustand des Täters und über die Verwahrungs-, Behandlungs- oder Pflegebedürftigkeit.
3.1.2 Das Gericht würdigt Gutachten grundsätzlich frei. In Fachfragen darf es davon indessen nicht ohne triftige Gründe abweichen, und Abweichungen müssen begründet werden. Umgekehrt kann das Abstellen auf nicht schlüssige Gutachten unter Verzicht auf die gebotenen zusätzlichen Beweiserhebungen im Sinne von Art. 9 BV willkürlich sein (BGE 133 II 384 E. 4.2.3; 132 II 257 E. 4.4.1; 130 I 337 E. 5.4.2; 129 I 49 E. 4). Das trifft etwa zu, wenn der Sachverständige die an ihn gestellten Fragen nicht beantwortet, wenn er seine Erkenntnisse und Schlussfolgerungen nicht begründet oder diese in sich widersprüchlich sind oder wenn die Expertise sonst wie an Mängeln krankt, die derart offensichtlich und auch ohne spezielles Fachwissen erkennbar sind, dass sie das Gericht nicht hätte übersehen dürfen.
3.1.3 Die Vorinstanz stellt bei der Entscheidfindung auf die Gutachten des FPD der Universität Bern vom 24. September 2008 und 30. Juni 2010 unter Einschluss der mündlichen Ausführungen der Sachverständigen anlässlich der Verhandlung vom 6. Mai 2011 ab. Entgegen der Kritik in der Beschwerde sind formelle Mängel beim Zustandekommen der Gutachten nicht auszumachen. Bei den begutachtenden Sachverständigen des FPD handelt es sich um ausgewiesene Fachärzte für Psychiatrie und Psychotherapie. Sie erfüllen beide die von Art. 56 Abs. 4 StGB und Art. 43 Ziff. 1 Abs. 3 aStGB gestellten Anforderungen (siehe vorstehend E. 1.2.5). Auch inhaltlich ist eine Mangelhaftigkeit der Gutachten nicht erkennbar. Diese legen offen, auf welchen Grundlagen sie beruhen (u.a. die Beurteilung der IFKGS vom 29. Oktober 2007), beschreiben Art und Weise der erfolgten körperlichen und psychiatrischen Untersuchungen, enthalten eine detaillierte Anamnese und Fremdanamnese, eine breit abgestützte Befunderhebung sowie eine aktuelle und retrospektive Diagnosestellung mit anschliessender umfassender Beantwortung der Beweisfragen. Die Gutachten sprechen sich zu allen relevanten Fragestellungen im Hinblick auf Art. 64 StGB und Art. 43 Ziff. 1 Abs. 2 aStGB aus, namentlich zum psychischen Gesundheitszustand des Beschwerdeführers, zur Deliktskausalität der psychischen Störungen, zur Rückfallgefährlichkeit, zur Therapiefähigkeit und -bereitschaft sowie zu den Erfolgsaussichten einer psychotherapeutischen stationären Behandlung und damit im Ergebnis auch zur Verwahrungsbedürftigkeit des Beschwerdeführers (vgl. Gutachten vom 24. September 2008, S. 36-50, S. 51-53; Ergänzungsgutachten vom 30. Juni 2010, S. 9-10). Die Schlussfolgerungen, welche anlässlich der mündlichen Gutachtensergänzung mit einlässlicher Begründung bestätigt werden (mündliche Gutachtensergänzung, Verhandlungsprotokoll, S. 2-6) sind kriterienorientiert, sachlich und transparent.
3.1.4 Aus den Gutachten inkl. mündlicher Gutachtensergänzung ergibt sich nichts, was darauf schliessen liesse, diese seien entsprechend den Behauptungen des Beschwerdeführers "unvollständig", "undeutlich", "ungenau" oder "widersprüchlich" (Beschwerde, S. 28-36, 38). Der Beschwerdeführer vermag denn auch keine gewichtigen Tatsachen oder Umstände zu nennen, welche die Überzeugungskraft der Expertisen in Frage stellen, geschweige denn ernstlich erschüttern würden. Seine Kritik verbleibt im Bereich des Unwesentlichen, wenn er beispielsweise geltend macht, seine Arbeitsleistung und sein klagloses Verhalten in der Strafanstalt würden nicht genügend berücksichtigt oder er habe entgegen der Darstellung der Sachverständigen kein Haus in Bosnien geerbt (Beschwerde, S. 31). Er zeigt keine substanziellen Mängel der Gutachten auf und legt nicht dar, inwiefern sich die angeblich unrichtigen oder ungenauen Annahmen der Sachverständigen auf die rechtlich relevanten Schlussfolgerungen auswirken könnten. Ihm nicht genehme Analysen und Fazite der Gutachter (beispielsweise zur Rückfallgefahr gegenüber den Eltern unter Berücksichtigung der "neuen" familiären Situation: Ergänzungsgutachten vom 30. Juni 2010, S. 10, mündliche Gutachtensergänzung, Verhandlungsprotokoll, S. 5) ersetzt er in rein appellatorischer Weise durch eigene, ihm günstiger und plausibler erscheinende Wertungen (Beschwerde, S. 32). Mit den Erwägungen der Vorinstanz, welche sich zu den Rügen betreffend formelle und inhaltliche Mängel der Gutachten einlässlich äussert und diese mit stichhaltigen Argumenten verwirft (vgl. Urteil, S. 10-13), befasst sich der Beschwerdeführer nicht ausreichend (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG). Er beschränkt sich darauf, die im kantonalen Verfahren bereits vorgebrachten Einwände gegen die Gutachten zu erneuern und der vorinstanzlichen Beweiswürdigung lediglich seine eigene abweichende Sicht der Dinge gegenüberzustellen. Damit kann Willkür (Art. 9 BV) nicht begründet werden.
3.1.5 Zusammenfassend ergibt sich, dass die Vorinstanz auf die Gutachten inklusive mündliche Gutachtensergänzung ohne Willkür abstellen und triftige Gründe für ein Abweichen davon verneinen durfte. Dass sie im angefochtenen Entscheid auf die Beurteilungen der IFKGS ergänzend Bezug nimmt, (insofern als sie darauf hinweist, sämtliche angewandten Prognoseinstrumente - also auch die von der IFKGS verwendete Methode nach dem "Dittmannkatalog" - hätten zu übereinstimmenden Resultaten betreffend die Risikoeinschätzung geführt), ist in keiner Hinsicht zu beanstanden (angefochtenes Urteil, S. 15). Die Einwände des Beschwerdeführers (Beschwerde, S. 25-28), die IFKGS-Beurteilungen erfüllten die Anforderungen an ein Sachverständigengutachten nicht und stünden mit Art. 75a i.V.m. Art. 62d Abs. 2 StGB nicht im Einklang, gehen offensichtlich an der Sache vorbei.
3.2 Die Verwahrung von psychisch gestörten Tätern nach Art. 64 Abs. 1 lit. b StGB und Art. 43 Ziff. 1 Abs. 2 aStGB setzt neben einer relevanten Anlasstat eine für die Delinquenz kausale bzw. konnexe psychische Störung von erheblicher Schwere sowie die ernsthafte Erwartung weiterer Delinquenz ("Taten dieser Art") voraus. Art. 64 Abs. 1 lit. b StGB setzt für die Verwahrung ausserdem die Behandlungsunfähigkeit bzw. Unbehandelbarkeit der Störung voraus. Auch wenn die übrigen Voraussetzungen im Sinne dieser Bestimmung erfüllt sind, ist die Anordnung der Verwahrung unzulässig, falls eine Massnahme nach Artikel 59 StGB Erfolg verspricht.
3.3 Der Beschwerdeführer macht geltend, es fehle für eine Verwahrung an den Voraussetzungen von Art. 64 Abs. 1 lit. b StGB. Ausserdem erweise sich eine solche als unverhältnismässig (Beschwerde, S. 38-46).
3.4 Die vom Beschwerdeführer begangenen Delikte des qualifizierten Raubs und der Gefährdung des Lebens bilden ohne weiteres ausreichende Anlasstaten im Sinne von Art. 64 Abs. 1 lit. b StGB und Art. 43 Ziff. 1 Abs. 2 aStGB. Er hat im Rahmen des Raubüberfalls auf eine Asylbewerberunterkunft fünf Asylbewerber mit einer durchgeladenen Ordonnanzpistole bedroht und sie mit Klebeband gefesselt, wobei er mindestens eines der Opfer in unmittelbare Lebensgefahr brachte, als sich bei einem Gerangel um die Waffe drei Schüsse lösten. Im Übrigen erfüllt er nach der zutreffenden Auffassung der Vorinstanz auch die Voraussetzungen gemäss Art. 42 Ziff. 1 aStGB insofern, als er schon zahlreiche Verbrechen oder Vergehen vorsätzlich verübte, die seinen Hang zu solchen Delikten aufzeigen. So hat der Beschwerdeführer bereits als 18-Jähriger gemeinsam mit Mittätern unter Verwendung eines Messers Raubüberfälle begangen. Nach Beendigung der Raubhandlungen wurde den jeweiligen Opfern die Bekanntgabe von Name und Adresse abgenötigt, um sie von einer Anzeigeerstellung abzuhalten (Urteil des Strafgerichts vom 2. Mai 2001). In den Jahren 2003 und 2004 hat der Beschwerdeführer, abgesehen vom Raubüberfall auf die Asylbewerberunterkunft, Betäubungsmittel verkauft, seinen Vater mit einem Teleskop-Schlagstock während längerer Zeit geschlagen, seiner Mutter ein Brotmesser an den Hals gehalten und ihr dort sowie an der Hand und am linken Unterschenkel Schnittverletzungen zugefügt, sie mit dem Knauf des Messers auf den Kopf geschlagen und ihr heftige Kniestösse versetzt, sowie beiden Eltern mit dem Tod gedroht für den Fall, dass sie die Polizei benachrichtigen würden.
3.5 Der Beschwerdeführer leidet gemäss den Gutachten an einer narzisstischen und paranoiden Persönlichkeitsstörung, welche in einem mittelbaren Zusammenhang mit den Delikten stehen. Die Störungen hätten sich in der Kindheit/Jugend entwickelt und seien seit dem früheren Erwachsenenalter (Anfang 20) manifest. Es handle sich um dauerhafte Störungen, die durch das ganze Leben hindurch getragen würden. Das Verhalten des Beschwerdeführers erweise sich in vielen persönlichen und sozialen Bereichen als unflexibel, unangepasst und unzweckmässig. Die Gutachter halten die diagnostizierten Störungen medizinisch für mittelgradig ausgeprägt. Sie sprechen von verfestigten und dauerhaften Erfahrungs- und Verhaltensmustern des Beschwerdeführers und von einer erheblichen Abweichung seines Seelenzustands von der gedachten Durchschnittsnorm (Gutachten vom 24. September 2008, S. 7, 53; mündliche Gutachtensergänzung, Verhandlungsprotokoll, S. 3, 6). Die Vorinstanz durfte unter diesen Umständen von der rechtlichen Relevanz der psychiatrischen Diagnose ausgehen und eine schwere psychische Störung im Sinne von Art. 64 Abs. 1 lit. b StGB und Art. 43 Ziff. 1 Abs. 2 aStGB annehmen (Urteil des Kassationshofs 6S.427/2005 vom 6. April 2006 E. 2.3 mit Hinweisen; HEER, Basler Kommentar, Strafrecht, Bd. I, Art. 64 Rz. 41 ff.; Basler Kommentar I, Art. 43 Rz. 152 ff.). Ebenso durfte sie gestützt auf die Gutachten ohne Bundesrechtsverletzung die Konnexität zwischen Anlasstaten und psychischen Störungen bejahen. Ein indirekter oder mittelbarer Zusammenhang genügt sowohl nach altem als auch nach neuem Recht (HEER, Basler Kommentar I, 2. Aufl., Art. 64 Rz. 43; Basler Kommentar I, Art. 43 Rz. 156). Die Kritik in der Beschwerde (S. 37) ist unbegründet.
3.6 3.6.1 Gemäss den Gutachten besteht eine erhebliche, generelle Rückfallgefahr. Es sei davon auszugehen, dass der Beschwerdeführer in Zukunft wieder im Sinne eines "Berufskriminellen" delinquieren werde. Zu erwarten seien mit grosser Wahrscheinlichkeit insbesondere Raubdelikte, wobei Gewalttaten bei Raubüberfällen namentlich zu befürchten seien, wenn sich die Opfer wehrten. Es sei jedoch nicht mit Overkill-Gewalttaten zu rechnen. Dass es im Rahmen einer Auseinandersetzung auch zu einer Tötung kommen könnte, sei zwar nicht ausgeschlossen. Es sei jedoch nicht davon auszugehen. Auch gegenüber den Eltern sei mit ähnlichen Delikten wie bisher zu rechnen, falls sich der Beschwerdeführer von diesen bzw. ihren Problemen nicht genügend distanzieren könne. Es bestehe insoweit eine Rückfallgefahr für Nötigungen und Tätlichkeiten. Die Legalprognose sei insgesamt sehr ungünstig (Gutachten vom 24. September 2008, S. 49; mündliche Gutachtensergänzung, Verhandlungsprotokoll, S. 5). Die IFKGS gelangt im Rahmen ihrer Gefährlichkeitsbeurteilung auf der Grundlage des "Dittmannkatalogs" zum selben Schluss (vgl. kantonale Akten, IFKGS-Beurteilungen vom 29. Oktober 2007 und 10. November 2008).
3.6.2 Angesichts der hohen Wahrscheinlichkeit weiterer Raubstraftaten im bisherigen Umfang durfte die Vorinstanz ohne Bundesrechtsverletzung eine qualifizierte Gefährlichkeit im Sinne von Art. 64 Abs. 1 lit. b StGB und Art. 43 Ziff. 1 Abs. 2 aStGB bejahen. Anlasstaten und zukünftige Delikte sind kongruent. Es besteht damit die erhebliche Gefahr weiterer schwerwiegender Straftaten. Der Einwand des Beschwerdeführers (Beschwerde, S. 45), er sei kein Mörder oder Sexualstraftäter, hilft ihm in der Sache ebenso wenig weiter wie das Vorbringen (Beschwerde, S. 24 f.), eine Legal- oder Gefährlichkeitsprognose liesse sich gar nicht erstellen. Die Risikobeurteilung bzw. die Einschätzung der Rückfallgefahr ist zwar schwierig, es stehen hierfür aber etablierte Instrumente zur Verfügung (vgl. HEER, Basler Kommentar I, 2. Aufl., Basel 2007, Art. 64 Rz. 60 ff.). Vorliegend erfolgte die Beurteilung der Rückfallgefahr auf der Grundlage verschiedener aktueller, fachlich etablierter Prognoseinstrumente (PCL-R, HCR-20). Über die Anwendung dieser Instrumente hinaus nahmen die Sachverständigen eine differenzierte Einzelfallanalyse mit einer Gesamtwürdigung von Tat und Täter vor. Damit liegt eine umfassende und nachvollziehbare Einschätzung der Risikokalkulation vor (vgl. HEER, Basler Kommentar I, 2. Aufl., Basel 2007, Art. 64 Rz. 70 ff.).
3.7 3.7.1 Art. 64 Abs. 1 lit. b StGB setzt für die Verwahrung psychisch gestörter, gefährlicher Täter die Behandlungsunfähigkeit bzw. Nichtbehandelbarkeit voraus. Die Verwahrung ist nur zulässig, wenn eine Massnahme nach Artikel 59 StGB keinen Erfolg verspricht. Nach der Rechtsprechung ist hievon auszugehen, wenn es unwahrscheinlich oder nicht hinreichend wahrscheinlich erscheint, dass die Gefahr weiterer Straftaten im Sinne von Art. 64 StGB innert fünf Jahren deutlich verringert werden kann (BGE 134 IV 315 E. 3.4.1; Urteil 6B_92/2010 vom 30. März 2010 E. 4.2). Der Behandlungsprognose kommt bei der (nachträglichen) Anordnung einer Verwahrung elementare Bedeutung zu.
3.7.2 Die Vorinstanz geht davon aus, dass eine stationäre therapeutische Behandlung nach Art. 59 StGB keinen Erfolg verspricht (angefochtenes Urteil, S. 14). Sie erachtet den Beschwerdeführer derzeit als nicht behandelbar. Schwergewichtig stellt sie dabei auf die von den Gutachtern in Frage gestellte Therapierbarkeit des Beschwerdeführers im Sinne einer Therapieunwilligkeit ab sowie darauf, dass die diagnostizierten Persönlichkeitsstörungen schwierig zu behandeln, die gängigen Therapieverfahren zumindest in Bezug auf störungs- und deliktorientierte Behandlungen nicht ausreichend und neue Verfahren in ihrer Wirksamkeit noch nicht belegt sind. Es sei deshalb nicht zu erwarten, dass der Beschwerdeführer von einer stationären Massnahme noch sonderlich profitieren könne (Gutachten vom 24. September 2008, S. 52; Ergänzungsgutachten vom 30. Juni 2010, S. 9).
3.7.3 Nach Lehre und Rechtsprechung sind an die Therapiewilligkeit keine allzu strengen Anforderungen zu stellen. Dies trägt dem Umstand Rechnung, dass es gerade aufgrund der psychischen Erkrankung des Betroffenen an der Fähigkeit fehlen kann, die Notwendigkeit und das Wesen einer Behandlung abzuschätzen. Mangelnde Einsicht gehört bei schweren, langandauernden Störungen häufig zum typischen Krankheitsbild. Ein erstes Therapieziel besteht daher oft darin, Einsicht und Therapiewilligkeit zu schaffen, was gerade im Rahmen stationärer Behandlungen auch Aussichten auf Erfolg hat (statt vieler Urteil 6B_373/2010 vom 13. Juli 2010 E. 5.5).
3.7.4 Davon muss auch hier ausgegangen werden, zumal die Gutachter - was die Vorinstanz bei der Würdigung der Behandlungsprognose ausser Acht lässt - ein "Sich-Einlassen-Können" des Beschwerdeführers auf eine individuelle Therapie (mit kognitiven Ansätzen) nicht auszuschliessen vermögen. Sie halten eine solche Therapie - bei an sich genereller Verneinung der Therapierbarkeit aufgrund der fixierten Sichtweise des Beschwerdeführers (insbesondere mündliche Gutachtensergänzung, Verhandlungsprotokoll, S. 5) - nicht für "unmöglich", sondern einfach für "schwierig" (vgl. Ergänzungsgutachten vom 30. Juni 2010, S. 9; mündliche Gutachtensergänzung, Verhandlungsprotokoll, S. 3). Die Erarbeitung einer Motivationsbasis sei denkbar, ebenso die Schaffung eines Veränderungswillens (mündliche Gutachtensergänzung, Verhandlungsprotokoll, S. 3). Damit relativieren die Gutachter ihre generellen Aussagen zur Therapieunwilligkeit des Beschwerdeführers. Sie sprechen einer stationären Behandlung mithin nicht jeglichen Erfolg ab. Wohl äussern sie sich zur Therapierbarkeit des Beschwerdeführers im Sinne einer Therapieunwilligkeit sehr skeptisch, nehmen aber entgegen der Vorinstanz nicht Unbehandelbarkeit an, sondern bejahen im Ergebnis wenigstens die Motivierbarkeit. Eine solche Motivierbarkeit kann nach der Rechtsprechung in einer Anfangsphase genügen (Urteil 6B_252/2010 vom 22. Juli 2010 E. 2.4 mit weiteren Hinweisen auf Rechtsprechung und Lehre). Dass der Beschwerdeführer therapeutische Massnahmen nicht kategorisch ablehnt, zeigt sich im Übrigen auch daran, dass er im Strafvollzug von sich aus und ohne entsprechende Verpflichtung einer therapeutischen Betreuung zunächst in zweiwöchentlichen, später in wöchentlichen Sitzungen nachging. Dass er diese Betreuung nach acht Monaten abgebrochen hat, weil sie ihn "in dieser Form nicht weiter brachte" bzw. er "sich nicht krank fühle" (vgl. angefochtenes Urteil, S. 11), mag zwar ein Indiz gegen seine Therapiewilligkeit bilden, stellt aber die Motivierbarkeit nicht in Frage.
3.7.5 Hinzu kommt, dass der heute 29-jährige Beschwerdeführer, welcher sich seit dem 19. Juli 2005 im Strafvollzug befindet, noch nie einer rechtsgenüglichen therapeutischen Behandlung zugeführt wurde. Zwar ist ein vorausgegangener Behandlungsversuch keine gesetzliche Voraussetzung für eine Verwahrung. Ob ein Straftäter behandelbar ist oder nicht, lässt sich aber unter Umständen zuverlässig erst entscheiden, wenn ein entsprechender Versuch mit adäquaten Mitteln unternommen wurde und gescheitert ist (vgl. GÜNTER STRATENWERTH, Schweizerisches Strafrecht, Allgemeiner Teil I, Strafen und Massnahmen, 2. Aufl., Bern 2006, § 8 Rz. 8; HEER, Basler Kommentar I, 2. Aufl., Basel 2007, Art. 64 Rz. 106 ff. mit weiteren Hinweisen; vgl. auch Urteil des Bundesgerichts 6S.386/2000 vom 1. September 2000 E. 3d). Davon ist hier mit Blick auf die Ausführungen der Sachverständigen auszugehen.
3.7.6 Unter Berücksichtigung dieser Umstände und in Anwendung des Verhältnismässigkeitsprinzips lässt sich die Anordnung der nachträglichen Verwahrung nicht rechtfertigen. Eine solche Massnahme hat Ausnahmecharakter und ist nur mit der gebotenen Zurückhaltung anzuordnen. Angesichts der sehr einschneidenden Eingriffe einer Verwahrung in die Persönlichkeits- und Freiheitsrechte des Betroffenen ist diese sichernde Massnahme "ultima ratio", was für die nachträgliche Verwahrung umso mehr gelten muss (vgl. auch BGE 137 IV 51 E. 6.2). Diese liesse sich ohne vorgängigen Behandlungsversuch bei einem jungen, noch nie einer therapeutischen Massnahme zugeführten Menschen nur vertreten, wenn unwahrscheinlich erschiene, dass eine adäquate Behandlung innert absehbarer Zeit, d.h. in der Regel innert fünf Jahren, zu einer das Rückfallrisiko erkennbar reduzierenden Entwicklung des Täters führte. Solches kann in Bezug auf den Beschwerdeführer mit Blick auf die Ausführungen der Gutachter nicht mit der nötigen Klarheit gesagt werden.
3.8 Die nachträgliche Anordnung der Verwahrung verletzt damit Bundesrecht. Der angefochtene Entscheid ist aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Die Vorinstanz wird prüfen, ob eine stationäre Massnahme nach Art. 65 Abs. 1 StGB anzuordnen ist (siehe hierzu insbesondere HEER, Basler Kommentar I, Basel 2007, 2. Aufl., Art. 65 Rz. 96). Art. 59 Abs. 3 StGB sieht hierfür ausdrücklich eine Unterbringung in einem sicheren Rahmen vor. Den Sicherheitsinteressen der Allgemeinheit wäre dadurch Rechnung getragen. Unter diesen Umständen müssen die Rügen des Beschwerdeführers in Bezug auf die geltend gemachte Verletzung des völkerrechtlichen Rückwirkungsverbots, des Legalitätsprinzips und des Doppelbestrafungsverbots nicht behandelt werden.
4. Die Beschwerde ist teilweise gutzuheissen. Im Übrigen ist sie abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens hat der Kanton Basel-Stadt den Beschwerdeführer im Umfang seines Obsiegens für das bundesgerichtliche Verfahren zu entschädigen (Art. 68 Abs. 1 BGG). Die Entschädigung wird praxisgemäss seinem Rechtsvertreter ausgerichtet. Insofern wird das Gesuch um unentgeltliche Rechtspflege gegenstandslos. Soweit der Beschwerdeführer mit seiner Beschwerde unterliegt, wird er kostenpflichtig (Art. 66 Abs. 1 BGG). Das Gesuch um Gewährung der unentgeltlichen Rechtspflege kann in diesem Umfang gutgeheissen werden. Seine Bedürftigkeit ist ausgewiesen (vgl. BGE 125 IV 161 E. 4) und die Beschwerde war nicht von vornherein aussichtslos. Es sind daher keine Kosten zu erheben (Art. 64 Abs. 1 BGG). Dem Vertreter ist aus der Bundesgerichtskasse eine reduzierte Entschädigung auszurichten (Art. 64 Abs. 2 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 6. Mai 2011 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird sie abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird, soweit es nicht gegenstandslos geworden ist, gutgeheissen. Dem Beschwerdeführer wird Rechtsanwalt Dieter Gysin als unentgeltlicher Rechtsbeistand beigegeben.
3. Es werden keine Kosten erhoben.
4. Der Kanton Basel-Stadt hat dem Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 2'000.-- auszurichten.
5. Dem Rechtsvertreter des Beschwerdeführers wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 1'000.-- aus der Bundesgerichtskasse ausgerichtet.
6. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt sowie der Staatsanwaltschaft des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 30. Januar 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill