Sachverhalt:
A. A.a X._ befindet sich seit dem 18. Mai 2009 in Untersuchungs- und Sicherheitshaft bzw. im vorzeitigen Strafvollzug. Am 10. Juni 2010 wurde er vom Strafgericht Basel-Stadt wegen vorsätzlicher Tötung schuldig gesprochen und unter Berücksichtigung einer vollziehbar erklärten Reststrafe zu einer Gesamtfreiheitsstrafe von sechseinhalb Jahren verurteilt. Hiergegen reichte er Berufung ein.
A.b Am 25. August 2011 stellte X._ ein Gesuch um Entlassung aus dem vorzeitigen Strafvollzug. Das Gesuch wurde vom Appellationsgericht des Kantons Basel-Stadt am 22. September 2011 abgewiesen.
A.c Mit Beschwerde in Strafsachen an das Bundesgericht vom 26. Oktober 2011 beantragte X._, den Entscheid des Appellationsgerichts aufzuheben. Er selbst sei aus dem vorzeitigen Strafvollzug zu entlassen, eventuell unter Anordnung von Ersatzmassnahmen. Subeventuell sei die Sache an die Vorinstanz zur Neuentscheidung zurückzuweisen. Am 10. November 2011 hiess das Bundesgericht die Beschwerde insbesondere wegen einer Verletzung des Begründungsgebots gut und wies die Sache an das Appellationsgericht zurück, damit dieses umgehend einen hinreichend begründeten und den gesetzlichen Formen genügenden Entscheid fälle. Überdies stellte das Bundesgericht einen Verstoss gegen das Beschleunigungsgebot fest, lehnte aber eine Entlassung aus dem vorzeitigen Strafvollzug ab, da Haftgründe nicht offensichtlich fehlten (Urteil 1B_608/2011).
A.d Am 24. November 2011 wies das Appellationsgericht das Gesuch um Entlassung aus dem vorzeitigen Strafvollzug ab.
B. Mit Eingabe vom 22. Dezember 2011 führt X._ wiederum Beschwerde beim Bundesgericht mit dem Antrag, den Entscheid des Appellationsgerichts aufzuheben. Überdies sei er aus dem vorzeitigen Strafvollzug zu entlassen, eventuell unter Anordnung von Ersatzmassnahmen. Sodann sei festzustellen, dass das Beschleunigungsgebot erneut verletzt worden sei.
C. Die Staatsanwaltschaft des Kantons Basel-Stadt hat innert Frist keine Vernehmlassung eingereicht. Das Appellationsgericht hat sich mit Eingabe vom 2. Januar 2012 zur Sache geäussert, ohne formell Antrag zu stellen. X._ hat auf eine weitere Stellungnahme verzichtet.

Erwägungen:
1. Weist das Bundesgericht eine Streitsache an die Vorinstanz zurück zu neuem Entscheid, so richtet sich die Anfechtbarkeit desselben nach den gleichen Regeln wie diejenige des in der früheren Phase überprüften und aufgehobenen Entscheids. Im vorliegenden Zusammenhang geht es um die vom Beschwerdeführer ersuchte Entlassung aus dem vorzeitigen Strafvollzug, mit dem die angeordnete Sicherheitshaft vollzogen wird (vgl. dazu <ref-law>). Gegen den angefochtenen Entscheid ist die Beschwerde in Strafsachen nach <ref-law> gegeben. Anwendbar ist die am 1. Januar 2011 in Kraft getretene Schweizerische Strafprozessordnung (siehe Art. 453 f. StPO). Danach ist der angefochtene Entscheid kantonal letztinstanzlich (Art. 222 i.V.m. <ref-law> analog, <ref-law>). Beim Entscheid des Appellationsgerichts handelt es sich um einen Zwischenentscheid, der einen nicht wieder gutzumachenden Nachteil im Sinne von <ref-law> 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 <ref-law> zur Beschwerde berechtigt. Das Bundesgericht kann nach <ref-law> bei Gutheissung der Beschwerde in der Sache selbst entscheiden. Der Antrag auf Haftentlassung ist somit zulässig. Auf die Beschwerde ist einzutreten (vgl. BGE 1B_608/2011 vom 10. November 2011, E. 1).
2. 2.1 Nach <ref-law> ist Untersuchungs- und 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 (Abs. 1 lit. c). Haft ist überdies zulässig, wenn ernsthaft zu befürchten ist, eine Person werde ihre Drohung, ein schweres Verbrechen auszuführen, wahrmachen (Abs. 2). Untersuchungs- und Sicherheitshaft können unter bestimmten Voraussetzungen wie hier in den vorzeitigen Strafvollzug überführt werden (vgl. <ref-law>). Das zuständige Gericht ordnet gemäss <ref-law> an Stelle der Haft eine oder mehrere mildere Massnahmen an, wenn sie den gleichen Zweck erfüllen.
2.2 Der Beschwerdeführer bestreitet den dringenden Tatverdacht nicht. Er rügt jedoch, die Vorinstanz habe den Haftgrund der Wiederholungsgefahr gemäss <ref-law> zu Unrecht bejaht.
2.3 Sinn und Zweck der Anordnung von Haft wegen Wiederholungs- bzw. Fortsetzungsgefahr ist die Verhütung von Delikten. <ref-law> setzt die ernsthafte Befürchtung voraus, dass die beschuldigte Person durch Delikte bestimmter Schwere die Sicherheit anderer erheblich gefährdet, nachdem sie bereits früher gleichartige Strafen verübt hat. Dabei ist <ref-law> dahingehend auszulegen, dass Verbrechen oder schwere Vergehen drohen müssen (<ref-ruling> E. 3.2 S. 85 f.). Verbrechen sind Taten, die mit Freiheitsstrafe von mehr als drei Jahren bedroht sind (<ref-law>); Vergehen sind solche, bei denen Freiheitsstrafe bis zu drei Jahren oder Geldstrafe droht (<ref-law>). Die Begehung der in <ref-law> 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 (<ref-ruling> E. 3.2 S. 86).
2.4 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. Sie können jedoch auch Gegenstand eines noch hängigen Strafverfahrens bilden, in dem sich die Frage der Untersuchungs- und Sicherheitshaft stellt. Allerdings muss mit an Sicherheit grenzender Wahrscheinlichkeit feststehen, dass die beschuldigte Person solche Straftaten begangen hat. Neben einer rechtskräftigen Verurteilung gilt der Nachweis auch bei einem glaubhaften Geständnis oder einer erdrückenden Beweislage als erbracht (<ref-ruling> E. 3.2 S. 86). Obwohl der Haftgrund der Wiederholungsgefahr grundsätzlich restriktiv zu handhaben ist (<ref-ruling> E. 3.2 S. 85; 135 I 71 E. 2.3, 2.6 und 2.11 S. 73 ff.), ergibt sich sodann aus einer systematisch-teleologischen Auslegung von <ref-law>, dass es selbst bei Fehlen von früheren gleichartigen Straftaten nicht in der Absicht des Gesetzgebers lag, mögliche Opfer von weiteren Gewaltdelikten erheblichen konkreten Risiken auszusetzen (vgl. <ref-ruling> E. 3 und 4 S. 18 ff.). Dem Grad der Gewaltbereitschaft der betroffenen Person kommt damit eine massgebliche Bedeutung zu.
2.5 Der Beschwerdeführer hat seine Verurteilung vom 10. Juni 2010 wegen vorsätzlicher Tötung angefochten. Dabei ist sein allfälliger Tatbeitrag umstritten. Weder liegt insofern ein Geständnis vor noch kann von einer derart erdrückenden Beweislage ausgegangen werden, dass praktisch in Vorwegnahme des Berufungsentscheids von einer erwiesenen Tatbegehung auszugehen wäre. Indessen enthält der angefochtene Entscheid eine umfangreiche Liste der früheren strafrechtlichen Verurteilungen des Beschwerdeführers. Die entsprechenden Feststellungen der Vorinstanz sind in der Sache nicht umstritten, entsprechen den Akten bzw. sind nicht offensichtlich unrichtig und daher für das Bundesgericht verbindlich (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG). Gestützt auf diese Feststellungen kommt das Appellationsgericht zum Schluss, die Straffälligkeit ziehe sich "wie ein roter Faden durch die letzten zehn Jahre des Lebens des Gesuchstellers vor seiner Verhaftung im Mai 2009". Der Beschwerdeführer wendet dagegen ein, eine Vielzahl der Verurteilungen beruhe auf Delikten, die nicht als schwerwiegende Vorfälle zu bezeichnen seien. Er anerkennt allerdings, dass es sich bei der Freiheitsberaubung zum Nachteil seiner damaligen Lebensgefährtin, weswegen er im Jahre 2005 verurteilt wurde, um ein Verbrechen im Gewaltbereich handelte. Trotzdem meint er, die Sicherheit anderer Personen insgesamt nicht erheblich gefährdet zu haben. Dies trifft indessen nicht zu. Abgesehen von der genannten Freiheitsberaubung, die schon für sich allein einen nicht zu unterschätzenden Hang zur Gewalt offenbart, hat sich der Beschwerdeführer auch in anderem Zusammenhang wiederholt gewaltbereit gezeigt. So war er im April 2007 an einem Raufhandel beteiligt, der auf einem Streit zwischen ihm selbst und seiner damaligen Freundin beruhte. Auch wenn der Beschwerdeführer dabei letztlich selbst verletzt wurde, manifestierte sich darin erneut seine Neigung zur Gewalt. Mehrfach liess sich der Beschwerdeführer sodann Gewalt und Drohung sowie Beschimpfungen bis hin zu Todesdrohungen gegenüber Behörden und Beamten zuschulden kommen. Die Gewaltbereitschaft des Beschwerdeführers, die sich wiederholt in Strafdelikten auszudrücken vermochte, ist damit erstellt.
2.6 In seiner Stellungnahme an das Bundesgericht macht das Appellationsgericht neu in Ergänzung des angefochtenen Entscheids unter Verweis auf die Akten geltend, der Beschwerdeführer habe auch seine damalige Freundin beschimpft und bedroht. Diese Vorgänge aus dem Jahre 2009 sind aktenkundig, und der Beschwerdeführer hatte die Gelegenheit, sich dazu zu äussern. Es ist daher jedenfalls zulässig, das unter dem Gesichtspunkt von <ref-law> mit zu berücksichtigen.
2.7 Schliesslich ist mit der Vorinstanz davon auszugehen, dass dem Beschwerdeführer im gegenwärtigen Zeitpunkt eine sehr ungünstige Rückfallprognose gestellt werden muss. Die bisherigen therapeutischen Bemühungen sind weitgehend gescheitert. Das schliesst künftige Erfolge nicht aus, lässt diese auf absehbare Zeit aber als nicht sehr wahrscheinlich erscheinen.
2.8 Insgesamt ist demnach ernsthaft zu befürchten, dass der Beschwerdeführer durch gleichartige Straftaten, d.h. durch weitere Gewaltdelikte, die Sicherheit anderer Personen erheblich gefährdet. Die Voraussetzungen von <ref-law> erweisen sich damit als erfüllt.
2.9 Infolgedessen muss nicht geprüft werden, ob die bereits erwähnten Drohungen des Beschwerdeführers gegenüber seiner früheren Freundin auch den Hafttatbestand von <ref-law> erfüllen würden, wieweit dies selbstständig eine Haft zu rechtfertigen vermöchte und wieweit es zulässig wäre, in diesem Sinne die Haftbegründung nachträglich zu erweitern.
3. 3.1 Der Beschwerdeführer erachtet die Haftanordnung als unverhältnismässig und sieht darin zugleich einen Verstoss gegen Art. 237 in Verbindung mit <ref-law>. Die Haft liesse sich in seinem Fall durch mildere Massnahmen ersetzen. Namentlich beantragt er die Haftentlassung nach Sicherstellung der folgenden Ersatzmassnahmen: den Nachweis einer Wohnmöglichkeit, die Betreuung durch die Bewährungshilfe, den Antritt einer Arbeit bzw. den Nachweis einer Tagesstruktur und die Durchführung einer ambulanten Psychotherapie.
3.2 Nach <ref-law> ordnet das zuständige Gericht an Stelle der Untersuchungs- oder Sicherheitshaft eine oder mehrere mildere Massnahmen an, wenn sie den gleichen Zweck wie die Haft erfüllen. Abs. 2 derselben Bestimmung enthält eine nicht abschliessende Aufzählung möglicher Ersatzmassnahmen wie die Sicherheitsleistung, die Ausweis- und Schriftensperre oder diverse Auflagen. <ref-law> schreibt in Umsetzung des allgemeinen Verhältnismässigkeitsgrundsatzes nach <ref-law> bzw., soweit es im vorliegenden Zusammenhang um einen Grundrechtseingriff geht, nach <ref-law> vor, dass Zwangsmassnahmen nur ergriffen werden können, wenn sich die damit angestrebten Ziele nicht durch mildere Massnahmen erreichen lassen.
3.3 Ersatzmassnahmen fallen in Betracht, wenn die Wiederholungsgefahr zwar gegeben ist, das Risiko eines Rückfalles sich aber durch ein milderes Mittel als die Haft massgeblich beschränken lässt (vgl. etwa <ref-ruling> sowie BGE 1B_237/2011 vom 7. Juni 2011, E. 7). Das trifft im vorliegenden Fall jedoch nicht zu. Weder die beantragten noch allfällige andere Ersatzmassnahmen vermögen die Wiederholungsgefahr auf Seiten des Beschwerdeführers zu beseitigen oder auch nur massgeblich zu beschränken. Die persönlichen Defizite des Beschwerdeführers sind, wie bereits dargelegt, nicht behoben. Mit seiner Neigung zur Gewalt ist weiterhin unverändert zu rechnen. Wie die Vergangenheit gezeigt hat , vermag namentlich ein fester Wohnsitz daran nichts zu ändern. Auch die Präventivwirkung der Bewährungshilfe oder einer Tagesstruktur ist weder ersichtlich noch wahrscheinlich. Dass eine ambulante Psychotherapie (im Sinne von <ref-law>) unter Umständen erfolgreich sein könnte, lässt sich zwar nicht von vornherein ausschliessen. Auch dazu zeigen die bisherigen schlechten Erfahrungen jedoch, dass der Erfolg einer solchen Behandlung zurzeit nicht gesichert oder wahrscheinlich ist. Die Vorinstanz hält dazu ausdrücklich fest, es sei dem Beschwerdeführer unbenommen bzw. sogar zu empfehlen, sich haftbegleitend einer delikts- und störungsspezifischen Verhaltenstherapie zu unterziehen, die bei einer nachweislich prognostischen Verbesserung in einem späteren Zeitpunkt zu einer erneuten Haftprüfung und allenfalls Haftentlassung führen könnte. Angesichts der fallspezifischen Umstände und der bisherigen negativen Erfahrungen erscheint es nicht unverhältnismässig, in diesem Sinne gewisse Anstrengungen des Beschwerdeführers zu verlangen, bevor Ersatzmassnahmen erneut geprüft und allenfalls aufgrund einer deutlich besseren Prognose angeordnet werden können.
3.4 Schliesslich beanstandet der Beschwerdeführer nicht, dass die bei einer definitiven Verurteilung zu erwartende Freiheitsstrafe die Dauer der Untersuchungs- und Sicherheitshaft bzw. des vorzeitigen Strafvollzugs von bisher rund zweieinhalb Jahren deutlich übersteigt. Mit dem noch nicht rechtskräftigen Urteil des Strafgerichts Basel-Stadt vom 10. Juni 2010 ist er denn auch zu einer Gesamtfreiheitsstrafe von sechseinhalb Jahren verurteilt worden. Der angefochtene Entscheid erweist sich demnach nicht als unverhältnismässig.
4. 4.1 Der Beschwerdeführer rügt, die Vorinstanz habe wie bei ihrem ersten Entscheid vom 22. September 2011 wiederum das Beschleunigungsgebot verletzt, indem sie den nunmehr angefochtenen Entscheid erst am 24. November 2011 und damit nach Ablauf der Frist von fünf Tagen gemäss <ref-law> gefällt habe.
4.2 Hebt das Bundesgericht einen ablehnenden Entscheid über ein Haftentlassungsgesuch auf und weist es die Sache zurück an das Berufungsgericht zur umgehenden Neubeurteilung, so befindet sich das Berufungsgericht grundsätzlich in der gleichen Situation, wie wenn bei ihm ein Gesuch um Haftentlassung eingeht. Damit rechtfertigt sich eine entsprechende verfahrensrechtliche Analogie. Demnach gilt <ref-law> auch in diesem Fall zumindest sinngemäss.
4.3 Bereits in seinem Urteil 1B_608/2011 vom 10. November 2011 in der gleichen Sache hatte sich das Bundesgericht mit der anwendbaren Frist zu befassen. Die einschlägige Bestimmung von <ref-law> sieht für Haftentlassungsgesuche während eines Verfahrens vor dem Berufungsgericht vor, dass die Verfahrensleitung des Berufungsgerichts innert fünf Tagen entscheidet. Diese Bestimmung ist auch anwendbar, wenn sich der Betroffene im vorzeitigen Straf- oder Massnahmenvollzug befindet (<ref-law>; <ref-ruling> E. 2 S. 275, E. 3.2.1 S. 277 mit Hinweisen; MARC FORSTER, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2011, N. 1 zu <ref-law>). Sie ist Ausdruck des strafprozessualen Beschleunigungsgebots in Haftsachen (<ref-law>, Art. 5 Ziff. 4 EMRK, <ref-law>). <ref-law> verweist zwar - im Unterschied zu Art. 230 Abs. 5 StPO - nicht ausdrücklich auf <ref-law> (vgl. dazu <ref-ruling> E. 3 S. 187 ff.). Es rechtfertigt sich aber aus Gründen der Gesetzessystematik sowie mit Blick auf die Notwendigkeit, ein rechtsstaatlich korrektes und dennoch rasches Verfahren zu gewährleisten, für den Beginn des Fristenlaufs in analoger Weise zur Regelung in <ref-law> grundsätzlich auf das Ende des Schriftenwechsels abzustellen (vgl. FORSTER, a.a.O. N. 4 zu <ref-law>, Fn. 21, sowie N. 5 zu Art. 228). Das setzt allerdings wiederum voraus, dass entsprechend kurze Fristen gesetzt werden, die gleichzeitig sowohl den Bedürfnissen der Betroffenen als auch der Komplexität des konkreten Falles, insbesondere der Schwere der sich stellenden Tat- und Rechtsfragen, gerecht werden.
4.4 Aus den Akten der Vorinstanz geht aufgrund des entsprechenden Eingangsstempels hervor, dass sie das Urteil des Bundesgerichts vom 10. November 2011, das am 15. November 2011 versandt worden war, am 16. November 2011 erhalten hat. Dem Beschwerdeführer wurde eine Frist zur Stellungnahme bis zum 23. November 2011 gesetzt. Diese diente dazu, ihm das rechtliche Gehör zu gewähren, und war kurz, aber sach- und fallgerecht. Seine Vernehmlassung ist denn auch bereits am 21. November 2011, also vor Ablauf der Frist, der Post aufgegeben worden und am 22. November 2011 beim Appellationsgericht eingegangen. Dieses fällte den angefochtenen Entscheid am 24. November 2011. Erging dieser Entscheid mithin innert zwei Tagen nach Ende des Schriftenwechsels, erweist sich die gesetzliche Vorschrift von <ref-law> und damit das Beschleunigungsgebot als gewahrt.
5. 5.1 Die Beschwerde ist unbegründet und abzuweisen.
5.2 Der unterliegende Beschwerdeführer stellt ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung. Seine Bedürftigkeit kann als erwiesen gelten. Da seine Begehren nicht als von vornherein aussichtslos erscheinen, ist seinem Gesuch stattzugeben. Damit sind für das bundesgerichtliche Verfahren keine Kosten zu erheben, und der Rechtsvertreter des Beschwerdeführers ist dafür aus der Bundesgerichtskasse angemessen zu entschädigen (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen, und es wird ihm für das bundesgerichtliche Verfahren Fürsprecher André Vogelsang als unentgeltlicher Anwalt beigegeben.
3. Es werden keine Kosten erhoben.
4. Fürsprecher André Vogelsang wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 2'000.-- aus der Bundesgerichtskasse ausgerichtet.
5. Dieses Urteil wird dem Beschwerdeführer sowie der Staatsanwaltschaft und dem Appellationsgericht des Kantons Basel-Stadt, Statthalterin, schriftlich mitgeteilt.
Lausanne, 16. Januar 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Aemisegger
Der Gerichtsschreiber: Uebersax