Sachverhalt:
A. A.a X._ wurde am 1. Januar 1997 vorläufig festgenommen und in der Folge in Untersuchungshaft und später in den vorzeitigen Strafvollzug versetzt. Mit Urteil vom 20. Januar 1999 stellte das Strafgericht Basel-Stadt fest, dass er verschiedene Straftatbestände erfüllt hatte, worunter (eventual)vorsätzliche Tötung, qualifizierten Raub und gewerbsmässigen Diebstahl. Wegen Unzurechnungsfähigkeit (gemäss Art. 10 StGB in der bis zum 31. Dezember 2006 geltenden Fassung; nachfolgend: aStGB) wurde er jedoch von der entsprechenden Anklage freigesprochen und in Anwendung von Art. 43 Ziff. 1 Abs. 1 aStGB in eine Heil- und Pflegeanstalt eingewiesen. Dem Urteil lag ein forensisch-psychiatrisches Gutachten der Universitären Psychiatrischen Kliniken Basel (UPK) vom 14. Januar 1998 zugrunde, wonach X._ an einer paranoiden Schizophrenie leide und ohne fachärztliche Behandlung bald wieder sein früheres Leben als sozial Randständiger aufnehme, wobei von einer forensisch massgeblichen Rückfallgefahr auszugehen sei; weil dies auch für Aggressionsdelikte zutreffe, seien ohne Behandlung die Voraussetzungen für eine Verwahrung nach Art. 43 Ziff. 1 Abs. 2 aStGB erfüllt. Am 2. Februar 1999 trat X._ in die UPK ein, von wo er am 29. April 1999 flüchtete.
A.b Am 4. April 2006 wurde X._ verhaftet und im Untersuchungsgefängnis Basel untergebracht. In einem weiteren forensisch-psychiatrischen Gutachten vom 29. November 2007 wurde in Übereinstimmung mit der ersten Expertise festgestellt, dass er an einer chronifizierten paranoiden Schizophrenie mit erheblichen psychotischen Symptomen leide; es bestehe eine deutlich erhöhte Gefahr, dass er in nicht ausreichend behandeltem Zustand in vergleichbaren Belastungssituationen erneut ähnlich gelagerte Delikte wie früher begehen könnte; angezeigt sei eine stationäre Massnahme gemäss Art. 59 StGB; sollte X._ für eine konsequent durchgeführte, hoch dosierte neuroleptische Behandlung nicht zu gewinnen oder sollte eine solche nicht wirksam sein, bestehe eine erhebliche Gefahr der Begehung von dem Tötungsdelikt ähnlichen Straftaten. Am 6. Oktober 2009 wurde X._ in die Etablissements de la plaine de l'Orbe (EPO) versetzt. Dieses erstattete am 31. Mai 2010 einen Vollzugs- und am 15. November 2010 einen Therapiebericht. Aus diesen geht hervor, dass X._ der Ansicht ist, das Tötungsdelikt in rechtfertigender Notwehr begangen zu haben, jegliche psychiatrische Erkrankung leugnet und sich weder einer psychopharmakologischen Medikation noch einer regelmässigen psychotherapeutischen Behandlung unterzieht.
A.c Am 21. Dezember 2010 beantragte das Ressort Strafvollzug des Kantons Basel-Stadt beim Strafgericht des Kantons Basel-Stadt gestützt auf Art. 62c Abs. 1 lit. a StGB die Aufhebung der Einweisung in eine Heil- und Pflegeanstalt sowie die Anordnung einer Verwahrung gemäss Art. 62c Abs. 4 StGB. Dieser schriftliche Antrag trägt den Eingangsstempel beim Strafgericht vom 28. Dezember 2010. Am 10. November 2011 erkundigte sich das Ressort Strafvollzug beim Strafgericht nach dem Verfahrensstand und ersuchte um Prüfung der Anordnung von Sicherheitshaft. In der Folge gab die Verfahrensleitung des Strafgerichts am 21. November 2011 bei der UPK ein psychiatrisches Gutachten in Auftrag zur Frage der Anordnung einer Verwahrung oder der Weiterführung der stationären Massnahme; überdies beantragte sie die Anordnung von Sicherheitshaft beim Zwangsmassnahmengericht.
A.d Am 24. November 2011 verfügte das Zwangsmassnahmengericht die Sicherheitshaft gegenüber X._ für die vorläufige Dauer von zwölf Wochen, d.h. bis zum 16. Februar 2012. Zur Begründung führte es im Wesentlichen aus, es liege ein so genanntes Nachverfahren vor, wobei eine hinreichende Wahrscheinlichkeit bestehe, dass dieses zu einer Massnahme führe, welche die Sicherstellung des Betroffenen erfordere. Zudem beruhe die Haft auf der gegebenen Flucht- und Fortsetzungsgefahr auf Seiten von X._ und sie sei auch verhältnismässig.
A.e Mit Entscheid vom 20. Dezember 2011 wies das Appellationsgericht des Kantons Basel-Stadt, Appellationsgerichtspräsident, eine gegen die Haftverfügung gerichtete Beschwerde von X._ ab.
B. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, der Entscheid des Appellationsgerichts sei aufzuheben und er sei umgehend aus der Haft zu entlassen. Überdies sei ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren. Zur Begründung wird im Wesentlichen geltend gemacht, über die Verlängerung der stationären Massnahme hätte spätestens am 25. Dezember 2010 entschieden werden müssen. Der entsprechende Antrag sei aber erst am 28. Dezember 2010 beim Strafgericht eingegangen. Der Freiheitsentzug sei danach ohne Entscheid über die Verlängerung der Massnahme oder die Anordnung von prozessualer Haft unrechtmässig während elf Monaten aufrecht erhalten worden, bis erst am 24. November 2011 der Entscheid über die Sicherheitshaft ergangen sei. Der Freiheitsentzug während dieser Dauer lasse sich nicht nachträglich anordnen bzw. rechtfertigen und sei ungesetzlich, weshalb X._ umgehend freizulassen sei.
C. Die Staatsanwaltschaft und das Appellationsgericht schliessen unter Verzicht auf weitere Ausführung auf Abweisung der Beschwerde. X._ hat ausdrücklich davon abgesehen, sich nochmals zur Sache zu äussern.
Erwägungen:
1. 1.1 Gegen den angefochtenen Entscheid ist die Beschwerde in Strafsachen nach Art. 78 ff. BGG gegeben. Anwendbar ist die am 1. Januar 2011 in Kraft getretene Schweizerische Strafprozessordnung (siehe Art. 448 ff. StPO). Danach ist der angefochtene Entscheid kantonal letztinstanzlich (Art. 80 BGG i.V.m. Art. 222 StPO analog; vgl. E. 2.4). Beim angefochtenen Entscheid handelt es sich um einen Zwischenentscheid, der einen nicht wieder gutzumachenden Nachteil im Sinne von Art. 93 Abs. 1 lit. a BGG bewirken kann. Der Beschwerdeführer nahm vor der Vorinstanz am Verfahren teil und hat ein rechtlich geschütztes Interesse an der Aufhebung des angefochtenen Entscheids. Er ist nach Art. 81 Abs. 1 BGG zur Beschwerde berechtigt. Das Bundesgericht kann nach Art. 107 Abs. 2 BGG bei Gutheissung der Beschwerde in der Sache selbst entscheiden. Der Antrag auf Haftentlassung ist somit zulässig (vgl. BGE 133 I 270 E. 1.1 S. 272 f.).
1.2 Freiheitsentzüge durch die Strafbehörden greifen in die Grundrechte der Betroffenen ein. Soweit es sich um strafprozessuale Zwangsmassnahmen handelt, dienen sie dazu, Beweise zu sichern, die Anwesenheit von Personen im Verfahren sicherzustellen oder die Vollstreckung des Endentscheids zu gewährleisten (Art. 196 lit. a-c StPO). Die Auslegung und die Anwendung der im Bundesrecht geregelten Voraussetzungen für die Grundrechtsbeschränkungen prüft das Bundesgericht mit freier Kognition (Art. 95 lit. a BGG; vgl. BGE 128 II 259 E. 3.3 S. 269). Auch mit dem Entscheid über strafprozessuale Zwangsmassnahmen wird über die Grundrechtsbeschränkung definitiv entschieden. Somit stellen solche Entscheide keine vorsorgliche Massnahmen im Sinne von Art. 98 BGG dar. Die nach dieser Bestimmung vorgeschriebene Beschränkung der Rügegründe und das über die Begründungspflicht nach Art. 42 Abs. 2 BGG hinausgehende Rügeprinzip im Sinne von Art. 106 Abs. 2 BGG sind demnach nicht anwendbar (vgl. BGE 1B_378/2011 vom 15. August 2011 E. 1.2).
1.3 Im vorliegenden Fall werden die tatsächlichen Feststellungen der Vorinstanz von keiner Seite in Frage gestellt. Da an deren Richtigkeit auch keine Zweifel bestehen, sind sie für das Bundesgericht verbindlich (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG).
2. 2.1 Streitgegenstand bildet die Zulässigkeit des Freiheitsentzugs des Beschwerdeführers während des vor dem Strafgericht als erster Instanz hängigen Verfahrens, in dem die Strafbehörden prüfen, ob die stationäre Massnahme zu verlängern oder allenfalls durch eine nachträgliche Verwahrung abzulösen ist. Die beiden Varianten beruhen zumindest teilweise auf unterschiedlichen gesetzlichen Grundlagen. Schon mit Blick auf Art. 5 Ziff. 1 EMRK und Art. 31 Abs. 1 BV muss ein Freiheitsentzug aber so oder so von der zuständigen Behörde verfügt werden und der Anspruch des Betroffenen auf Anrufung des Gerichts gewahrt bleiben.
2.2 Als eine mögliche Sanktion steht die Verlängerung der stationären Massnahme in Frage.
2.2.1 Gemäss Art. 59 Abs. 4 StGB beträgt der mit einer stationären Behandlung verbundene Freiheitsentzug in der Regel höchstens fünf Jahre. Sind die Voraussetzungen für die bedingte Entlassung nach fünf Jahren noch nicht gegeben und ist zu erwarten, durch die Fortführung der Massnahme lasse sich der Gefahr weiterer mit der psychischen Störung des Täters in Zusammenhang stehender Verbrechen und Vergehen begegnen, so kann das Gericht auf Antrag der Vollzugsbehörde die Verlängerung der Massnahme um jeweils höchstens fünf Jahre anordnen.
2.2.2 Nach Art. 59 Abs. 4 StGB entscheidet somit das Gericht und nicht die Vollzugsbehörde, die lediglich das Antragsrecht dazu besitzt, über die allfällige Verlängerung einer stationären therapeutischen Massnahme bzw. den damit verbundenen Freiheitsentzug nach Ablauf von höchstens fünf Jahren. Es ist im vorliegenden Fall unter den Verfahrensbeteiligten strittig, ob dieser Entscheid vor diesem Zeitpunkt zu ergehen hat oder der Antrag der Vollzugsbehörde für die Fristwahrung genügt. Ein solcher Antrag ersetzt jedoch so oder so den richterlichen Entscheid nicht.
2.2.3 Zulässig erscheint daher nur, dass entweder der eigentliche Entscheid über die Fortführung der Massnahme in der Sache vor Ablauf der fraglichen Frist ergeht oder dass, falls sich dieses Verfahren nicht rechtzeitig durchführen lässt, vor Ablauf der Frist allenfalls vom dafür zuständigen Gericht mit Blick auf das hängige Verlängerungsverfahren Sicherheitshaft angeordnet wird. Beim Entscheid über die Weiterführung der stationären Massnahme handelt es sich um einen selbstständigen nachträglichen Entscheid nach Art. 363 ff. StPO (vgl. die Botschaft zur Vereinheitlichung des Strafprozessrechts vom 21. Dezember 2005 in BBl 2006 1298), für den gemäss Art. 363 Abs. 1 StPO das Gericht zuständig ist, das schon das erstinstanzliche Urteil gefällt hat, sofern Bund oder Kantone nichts anderes bestimmen. Gemäss der nicht bestrittenen Feststellung der Vorinstanz kennt der Kanton Basel-Stadt keine davon abweichende Regelung.
2.3 Als zweite Variante steht im vorliegenden Fall die Ablösung der bisherigen stationären Massnahme durch eine nachträgliche Verwahrung zur Diskussion. Nach Art. 62c Abs. 4 StGB kann das Gericht bei Aufhebung einer Massnahme, die auf einer Straftat nach Art. 64 Abs. 1 StGB (wie insbesondere Mord, vorsätzliche Tötung, schwere Körperverletzung, Raub) beruht, auf Antrag der Vollzugsbehörde die Verwahrung anordnen, wenn ernsthaft zu erwarten ist, dass der Täter weitere Taten dieser Art begeht. Da der Beschwerdeführer unter anderem die Tatbestände der vorsätzlichen Tötung sowie des qualifizierten Raubs erfüllt hat, liegt nach vorläufiger Einschätzung trotz fehlender Schuldfähigkeit eine Anlasstat vor, die zu einer nachträglichen Verwahrung führen kann. Auch hierbei handelt es sich um einen selbstständigen nachträglichen Entscheid des Gerichts nach Art. 363 ff. StPO (vgl. erneut BBl 2006 1298), für den dieselben prozessualen Regeln gelten.
2.4 Eine besondere Regelung für die Anordnung von Sicherheitshaft enthalten die Art. 363 ff. StPO nicht (vgl. MARIANNE HEEr, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2011, N. 9 zu Art. 364 StPO). Aus der Zuständigkeitsregel von Art. 363 Abs. 1 StPO lässt sich jedoch auch die Anwendung der für das erstinstanzliche Verfahren geltenden Bestimmungen der Strafprozessordnung ableiten (vgl. in analogem Sinne BGE 1B_378/2011 vom 15. August 2011 E. 2.2.2). Wird während des Verfahrens Sicherheitshaft verfügt, sind mithin die Art. 220 ff. und 229 ff. StPO einschlägig, was die Zuständigkeit des Zwangsmassnahmengerichts für die prozessuale Haft mit sich bringt.
2.5 Was den vom Beschwerdeführer angerufenen Entscheid des Europäischen Gerichtshofs für Menschenrechte in Sachen Borer gegen Schweizerische Eidgenossenschaft vom 10. Juni 2010 (Urteil des EGMR Nr. 22493/06) betrifft, so bezieht sich dieser Entscheid nicht auf die damals noch nicht in Kraft stehende Schweizerische Strafprozessordnung, sondern auf die frühere Strafprozessordnung des Kantons Basel-Stadt, die terminologisch nicht zwischen Untersuchungs- und Sicherheitshaft unterschied (vgl. BGE 1B_378/2011 vom 15. August 2011 E. 2.2.2). Nach dem anwendbaren Übergangsrecht (vgl. Art. 448, 449 und 451 StPO) gilt im vorliegenden Fall das neue eidgenössische Verfahrensrecht mit der entsprechenden neuen Zuständigkeitsordnung. Der angerufene Entscheid des Europäischen Gerichtshofes ist damit nicht einschlägig.
2.6 Mit dem Gesuch des Ressorts Strafvollzug vom 21. Dezember 2010 wurde die vorliegende Angelegenheit wieder dem Strafgericht erster Instanz vorgelegt. Diesem obliegt der Entscheid in der Sache und allenfalls über den damit verbundenen Freiheitsentzug. Das Strafgericht hat aber darüber noch nicht entschieden. Für allfällige Sicherheitshaft während des hängigen Verfahrens ist hingegen das Zwangsmassnahmengericht zuständig. Die Vorinstanz geht selbst davon aus, die Regeldauer von fünf Jahren für eine stationäre Massnahme sei für diejenige des Beschwerdeführers am 25. Dezember 2010 abgelaufen. Darauf ist nicht zurückzukommen, nachdem der Beschwerdeführer nicht mehr, wie offenbar noch vor dem Appellationsgericht, geltend macht, die frühere Haft vom 1. Januar 1997 bis zum Urteil des Strafgerichts müsse in die Berechnung mit einbezogen werden. Der Antrag des Ressorts Strafvollzug auf Weiterführung des Freiheitsentzugs datiert zwar vom 21. Dezember 2010, trägt aber den Eingangsstempel des Strafgerichts vom 28. Dezember 2010. Vor Ablauf des mit der stationären Massnahme verbundenen Freiheitsentzugs am 25. Dezember 2010 wurde demnach nicht über einen Freiheitsentzug gerichtlich entschieden. Nachdem sich das Ressort Strafvollzug mit Schreiben vom 16. November 2011 beim Strafgericht über den Verfahrensstand erkundigt hatte, stellte dieses am 21. November 2011 den Antrag beim Zwangsmassnahmengericht, für das laufende Verfahren die Sicherheitshaft anzuordnen. Dieses verfügte die Haft am 24. November 2011. Der Beschwerdeführer befand sich damit vom 26. Dezember 2010 bis zum 24. November 2011, also für eine Dauer von praktisch elf Monaten, ohne richterlichen Entscheid in Haft. In diesem Sinne erweist sich sein Freiheitsentzug als grundsätzlich unrechtmässig.
3. 3.1 Zu prüfen ist, welche Folgen mit der Nichtbeachtung des Erfordernisses eines rechtzeitigen richterlichen Entscheides über die Weiterführung des Freiheitsentzugs verbunden sind.
3.2 Gemäss der bundesgerichtlichen Rechtsprechung kann die Verletzung der Verfahrensregeln im Zusammenhang mit der Anordnung von Präventivhaft, insbesondere das Fehlen eines nach den gesetzlichen Vorschriften im Sinne von Art. 31 Abs. 1 BV und Art. 5 Ziff. 1 EMRK ergangenen Hafttitels, verschiedene Rechtsfolgen mit sich bringen. Namentlich ist ihr mit der Feststellung der Unrechtmässigkeit der Haft, der teilweisen Gutheissung einer allfälligen Beschwerde in diesem Sinne sowie der Auflage der Verfahrenskosten im entsprechenden Umfang zulasten des Staates zu begegnen. Überdies kann der Betroffene, je nach der Schwere der Gesetzwidrigkeit, ein Entschädigungsverfahren nach Art. 429 ff. StPO, insbesondere Art. 431 StPO, einleiten (vgl. insbes. BGE 1B_683/2011 vom 5. Januar 2012 E. 2.2.1 sowie BGE 137 IV 92 E. 3 S. 96, 118; 136 I 274 E. 2.3 S. 278).
3.3 Hingegen rechtfertigt das Fehlen eines gültigen Hafttitels während einer gewissen Zeitdauer für sich allein eine Haftentlassung nicht, wenn und solange die materiellen Voraussetzungen eines Freiheitsentzugs erfüllt sind (vgl. BGE 1B_683/2011 vom 5. Januar 2012 E. 2.2.2 mit weiteren Hinweisen auf die bundesgerichtliche Rechtsprechung). Immerhin müssen die öffentlichen Interessen für die Weiterführung des Freiheitsentzugs, insbesondere die Sicherheitsinteressen für die Fortsetzung von Sicherheitshaft, desto grösser sein, je länger diese bereits ohne gültigen Titel gedauert hat. Der Gefahr für die Öffentlichkeit, die vom Häftling ausgeht, kommt daher mit zunehmender Dauer eine ebenfalls grössere Bedeutung zu. Mit Blick auf Art. 196 lit. c StPO muss auch eine gewisse Wahrscheinlichkeit dafür bestehen, dass eine strafrechtliche Sanktion ausgesprochen wird, und der Betroffene nicht nur prozessual ohne späteren strafrechtlichen Freiheitsentzug in Haft genommen bzw. belassen wird.
3.4 Nach Art. 221 Abs. 1 lit. c StPO ist Sicherheitshaft unter anderem dann zulässig, wenn die beschuldigte Person eines Verbrechens oder Vergehens dringend verdächtig und ernsthaft zu befürchten ist, dass sie durch schwere Verbrechen oder Vergehen die Sicherheit anderer erheblich gefährdet, nachdem sie bereits früher gleichartige Straftaten verübt hat.
3.4.1 Der dringende Tatverdacht spielt im vorliegenden Fall keine Rolle mehr, nachdem rechtskräftig strafrichterlich festgestellt ist, dass der Beschwerdeführer die Tatbestände verschiedener Strafdelikte erfüllt hat, auch wenn er mangels Zurechnungsfähigkeit freigesprochen wurde.
3.4.2 Massgeblicher Haftgrund ist hier die Wiederholungs- bzw. Fortsetzungsgefahr, die mit einer allfälligen Freilassung des Beschwerdeführers vor dem Entscheid in der Sache verbunden wäre. Sinn und Zweck dieses Haftgrunds bildet die Verhütung von Delikten. Art. 221 Abs. 1 lit. c StPO setzt die ernsthafte Befürchtung voraus, dass die beschuldigte Person durch Delikte von bestimmter Schwere die Sicherheit anderer erheblich gefährdet, nachdem sie bereits früher gleichartige Strafen verübt hat. Dabei ist Art. 221 Abs. 1 lit. c StPO dahingehend auszulegen, dass Verbrechen oder schwere Vergehen drohen müssen (BGE 137 IV 84 E. 3.2 S. 85 f.). Die Begehung der in Art. 221 Abs. 1 lit. c StPO genannten Delikte muss ernsthaft zu befürchten sein. Erforderlich ist eine sehr ungünstige Rückfallprognose; dabei sind insbesondere die Häufigkeit und Intensität der untersuchten Delikte sowie die einschlägigen Vorstrafen zu berücksichtigen (BGE 137 IV 84 E. 3.2 S. 86).
3.4.3 Bei den vom Gesetz verlangten Vortaten muss es sich ebenfalls um Verbrechen oder schwere Vergehen gegen gleiche oder gleichartige Rechtsgüter gehandelt haben. Die früher begangenen Straftaten können sich aus rechtskräftig abgeschlossenen früheren Strafverfahren ergeben. Dabei kommt dem Grad der Gewaltbereitschaft der betroffenen Person eine massgebliche Bedeutung zu (vgl. BGE 1B_722/2011 vom 16. Januar 2012 E. 2.4).
3.5 Der Beschwerdeführer hat schwere Delikte (vorsätzliche Tötung, qualifizierter Raub, gewerbsmässiger Diebstahl) begangen und dabei teilweise erhebliche Gewalt ausgeübt. Auch wenn er dafür strafrechtlich wegen Unzurechnungsfähigkeit nicht verurteilt werden konnte, ergeben sie sich aus einem rechtskräftig abgeschlossenen Strafverfahren und offenbart sein Verhalten eine grosse Gewaltbereitschaft. Die vorhandenen Gutachten, worunter auch das aktuellste vom 29. November 2007, gehen bei einer nicht ausreichenden Behandlung von einer erheblichen Rückfallgefahr mit Aggressionspotenzial bzw. dem Risiko der Begehung gleichartiger Delikte wie früher aus. Aus den Berichten der Vollzugsanstalt geht überdies hervor, dass sich der Beschwerdeführer weder einer psychopharmakologischen Medikation noch einer regelmässigen psychotherapeutischen Behandlung unterzieht. Damit ist eine massgebliche Rückfallgefahr verbunden mit einem erheblichen Sicherheitsrisiko ausgewiesen. Die Wahrscheinlichkeit, dass erneut eine strafrechtliche Sanktion in Form einer Massnahme in Verbindung mit einem Freiheitsentzug ausgesprochen wird, erscheint hoch. Die Voraussetzungen der Anordnung von Sicherheitshaft erweisen sich demnach als grundsätzlich erfüllt.
3.6 Der Beschwerdeführer befand sich während fast elf Monaten ohne gültigen Titel in Haft. Diese Dauer erscheint sehr lang (vgl. im Vergleich dazu die rund sechswöchige Haft ohne gültigen Titel in BGE 1B_683/2011 vom 5. Januar 2012). Die Fortsetzung der Haft erfordert daher erhebliche Sicherheitsinteressen. Allerdings geht vom Beschwerdeführer ein grosses Sicherheitsrisiko aus, das sich besonders durch das vorhandene Aggressionspotenzial auszeichnet, wobei er sich weigert, diesem therapeutisch entgegenzuwirken. Die Gefahr für die Öffentlichkeit bei einer Freilassung des Beschwerdeführers ist daher erheblich und im Übrigen teilweise selbstverschuldet. Eine umgehende Haftentlassung rechtfertigt sich unter diesen Umständen nicht.
3.7 Immerhin stellt sich ernsthaft die Frage einer allfälligen Haftentschädigung bzw. Genugtuung für die Dauer des Freiheitsentzugs ohne gültigen Titel (vgl. Art. 429 ff., insbes. Art. 431, StPO). Soweit sich das aus den dem Bundesgericht vorliegenden Akten ergibt, scheint der Beschwerdeführer allerdings während dieser Dauer nie um Haftentlassung ersucht zu haben. Es ist freilich auch nicht bekannt, ob der Beschwerdeführer Kenntnis von den rechtlichen Zusammenhängen hatte oder im massgeblichen Zeitraum anwaltlich vertreten war. Sowohl das Ressort Strafvollzug (seit Anordnung der stationären Massnahme mit dem Urteil des Strafgerichts vom 20. Januar 1999 bzw. seit der erneuten Festnahme des Beschwerdeführers nach seiner zwischenzeitlichen Flucht am 4. April 2006) als auch das Strafgericht (seit dem Eingang des Gesuchs um nachträgliche Verwahrung am 28. Dezember 2010) waren jedoch mit dem Fall befasst. Grundsätzlich oblag es beiden Behörden, von Amtes wegen zu prüfen, ob sich der Beschwerdeführer rechtmässig in Haft befand oder ob ein entsprechender Handlungsbedarf, namentlich im Hinblick auf den erforderlichen richterlichen Entscheid, bestand. Die Frage einer Haftentschädigung bzw. Genugtuung bildet jedoch nicht Streitgegenstand im vorliegenden Verfahren, weshalb sie hier nicht weiter zu prüfen ist.
4. 4.1 Demnach ist die Beschwerde teilweise gutzuheissen, und es ist festzustellen, dass die Haft während der Dauer vom 25. Dezember 2010 bis zum 24. November 2011 nicht auf einem richterlichen Entscheid beruhte, der die gesetzlichen Anforderungen gemäss Art. 31 Abs. 1 BV und Art. 5 Ziff. 1 EMRK erfüllte. Im Übrigen ist die Beschwerde abzuweisen. Das umfasst insbesondere das Gesuch um Haftentlassung, womit der Beschwerdeführer in Haft bleibt.
4.2 Bei diesem Verfahrensausgang sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (vgl. Art. 68 BGG). Damit ist das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung als gegenstandslos abzuschreiben.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, und es wird festgestellt, dass die Haft des Beschwerdeführers während der Dauer vom 25. Dezember 2010 bis zum 24. November 2011 nicht auf einem richterlichen Entscheid beruhte, der die gesetzlichen Anforderungen gemäss Art. 31 Abs. 1 BV und Art. 5 Ziff. 1 EMRK erfüllte. Im Übrigen wird die Beschwerde abgewiesen.
2. Es werden keine Kosten erhoben.
3. Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
5. Dieses Urteil wird dem Beschwerdeführer sowie der Staatsanwaltschaft und dem Appellationsgericht des Kantons Basel-Stadt, Appellationsgerichtspräsident, schriftlich mitgeteilt.
Lausanne, 27. Januar 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Uebersax