Sachverhalt:
A. Das Strafgericht Basel-Stadt verurteilte X._ am 12. September 2008 wegen versuchter vorsätzlicher Tötung und versuchten Mordes seiner Ehefrau zu einer Freiheitsstrafe von 13 Jahren. Es widerrief ausserdem die am 20. Juli 2006 gegen ihn ausgesprochene bedingte Freiheitsstrafe von 18 Monaten und auferlegte ihm Schadenersatz- und Genugtuungszahlungen von rund Fr. 42'000.--.
Die Staatsanwaltschaft Basel-Stadt hatte bei den Universitären Psychiatrischen Kliniken Basel (UPK) ein forensisch-psychiatrisches Gutachten über X._ eingeholt. In diesem kam Dr. med. A._ am 26. August 2008 zum Schluss, dass im Tatzeitpunkt keine Verminderung der Einsichtsfähigkeit vorlag (Gutachten 2008, S. 29, pag. 819 der Vorakten). Das ebenfalls von Dr. A._ erstellte Gutachten vom 6. Juli 2006 hielt demgegenüber fest, die durch einen Auto-Selbstunfall vom 26. Juli 2003 erlittenen Schädel-Hirnverletzungen hätten bei X._ zu einem organischen Psychosyndrom geführt. Gemäss Gutachten war für eine allmähliche Verbesserung der Symptomatik eine mehrjährige Therapie notwendig (Gutachten 2006, S. 31, pag. 49 der Vorakten).
Im Rahmen der Hauptverhandlung des Strafgerichts Basel-Stadt erläuterte Dr. med. B._, Chefarzt Forensische Psychiatrische Klinik der UPK, als Sachverständiger die beiden Gutachten.
B. Die gegen dieses Urteil von X._ erhobene Appellation hiess das Appellationsgericht des Kantons Basel-Stadt am 23. August 2011 teilweise gut und reduzierte die Strafsanktion auf zwölf Jahre Freiheitsstrafe. Im Übrigen bestätigte es das angefochtene Urteil. Insbesondere lehnte es die von X._ gerügte Befangenheit von Dr. B._ und Dr. A._ ab, da das bei Prof. Dr. med. C._ vom Forensisch-Psychiatrischen Dienst (FPD) der Universität Bern eingeholte Ergänzungsgutachten zum Schluss kam, dass Dr. A._ sein Gutachten lege artis erstellt hatte.
C. X._ führt Beschwerde in Strafsachen mit dem Antrag, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 23. August 2011 aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Diese sei anzuweisen, einen unbefangenen und unabhängigen Gutachter einzusetzen und mit der Begutachtung des Beschwerdeführers zu beauftragen. Ihm sei zudem die unentgeltliche Prozessführung und Verbeiständung zu bewilligen.
D. Das Appellationsgericht und die Staatsanwaltschaft des Kantons Basel-Stadt beantragen, die Beschwerde sei abzuweisen. Der Beschwerdeführer hat Bemerkungen zu den Vernehmlassungsantworten eingereicht.

Erwägungen:
1.1 1.1.1 Der Beschwerdeführer rügt, die Vorinstanz verletze den Anspruch auf unabhängige und unparteiische Richter sowie Sachverständige, da sie die von ihm rechtzeitig vorgebrachten Ablehnungsgründe von Dr. B._ und Dr. A._ verneine. Es erscheine in höchstem Masse problematisch, dass dieselbe Klinik (die UPK) die laufende Massnahme überwache, steuere und kontrolliere sowie nach einer internen Krisensitzung auch noch einen Gutachterauftrag übernehme. Die UPK habe diesen Auftrag nicht mit der notwendigen Unabhängigkeit wahrnehmen können. Der Fall sei für die Annahme einer Befangenheit exemplarisch. Das Gutachten hätte bei einer unabhängigen Institution in Auftrag gegeben werden müssen (Beschwerde, S. 8 ff.). Konkret erachtet der Beschwerdeführer Dr. A._ als befangen, weil dessen direkter Vorgesetzter, Dr. B._, parallel die Therapie des behandelnden Arztes Dr. med. D._ überwacht habe. Zudem sei Dr. B._ befangen, weil dieser die ambulante Therapie von Dr. D._ überwacht und eng mit diesem zusammengearbeitet habe. Am 11. Dezember 2007 habe als Folge der inkriminierten Taten eine gemeinsame Krisensitzung mit Prof. Dr. med. E._, Dr. B._, Dr. D._ und Dr. A._ stattgefunden. Dabei sei besprochen worden, ob beim Vorgehen von Dr. D._ oder bei der Überwachung der Massnahme durch die UPK Fehler passiert seien (Beschwerde, S. 5 ff.).
1.1.2 Der Beschwerdeführer argumentiert weiter, mit einer Gutachtensergänzung könne die Befangenheitsproblematik nicht behoben werden, da es das Gutachten lediglich ergänze und nicht beseitige. Er habe nie behauptet, das Gutachten vom 28. August 2008 sei nicht schlüssig oder überzeugend. Die sachverständigen Erläuterungen in der erstinstanzlichen Hauptverhandlung und das Gutachten seien vielmehr von Personen vorgenommen bzw. erarbeitet worden, bei denen der Anschein der Befangen- und der Unvoreingenommenheit objektiv begründet gewesen sei. Die Amtshandlungen hätten entsprechend wiederholt werden müssen (Beschwerde, S. 11 f.).
1.1.3 Der Beschwerdeführer rügt eine Verletzung von <ref-law>. Die Vorinstanz lasse unberücksichtigt, dass <ref-law> im Falle einer Straftat gemäss <ref-law> einen Sachverständigen voraussetze, der den Täter weder behandelt noch in anderer Weise betreut habe. Unvereinbar sei mit diesen Bestimmungen, dass Prof. E._ zum einen das Gutachten vom 26. August 2008 mitverantwortet und mitunterschrieben und gleichzeitig als Chef die Verantwortung für die Überwachung und Betreuung einer Massnahme in derselben Klinik innegehabt habe. Gleichermassen unzulässig sei der Auftritt von Dr. B._ als Sachverständiger vor Gericht gewesen, da er die Massnahme persönlich betreut habe. Zudem hätten sowohl Prof. E._ wie Dr. B._ an der besagten Krisensitzung teilgenommen.
1.1.4 Die angebliche Verspätung der Befangenheitsrüge ist nach Ansicht des Beschwerdeführers irrelevant, da diese nach <ref-law> von Amtes wegen hätte berücksichtigt werden müssen. Sein Verteidiger habe jedoch ohnehin nicht treuwidrig mit dem Ablehnungsgesuch zugewartet. Nach der ersten Akteneinsicht habe dieser nicht sämtliche Zusammenhänge realisiert. Das Gutachten vom 26. August 2008 habe die Zusammenarbeit der UPK mit dem behandelnden Arzt, Dr. D._, nicht erwähnt. Der Rechtsvertreter habe unmittelbar die Befangenheit gerügt, als ihm klar geworden sei, in welchem Ausmass die Beteiligten zusammengearbeitet hätten (Beschwerde, S. 11).
1.1.4 Die angebliche Verspätung der Befangenheitsrüge ist nach Ansicht des Beschwerdeführers irrelevant, da diese nach <ref-law> von Amtes wegen hätte berücksichtigt werden müssen. Sein Verteidiger habe jedoch ohnehin nicht treuwidrig mit dem Ablehnungsgesuch zugewartet. Nach der ersten Akteneinsicht habe dieser nicht sämtliche Zusammenhänge realisiert. Das Gutachten vom 26. August 2008 habe die Zusammenarbeit der UPK mit dem behandelnden Arzt, Dr. D._, nicht erwähnt. Der Rechtsvertreter habe unmittelbar die Befangenheit gerügt, als ihm klar geworden sei, in welchem Ausmass die Beteiligten zusammengearbeitet hätten (Beschwerde, S. 11).
1.2 1.2.1 Die Vorinstanz erwägt, die vom Beschwerdeführer geltend gemachten Ausstands- bzw. Ablehnungsgründe seien verspätet. Aus dem Gebot von Treu und Glauben folge, dass solche Einwände vorgebracht werden müssten, sobald sie der betreffenden Person bekannt seien. Der stets anwaltlich vertretene Beschwerdeführer hätte gegen den Gutachtensauftrag an die UPK opponieren müssen. Ab dem 8. Februar 2008 sei bekannt gewesen, dass Dr. A._ innerhalb der UPK das in Auftrag gegebene Gutachten verfassen würde. Der Rechtsvertreter hätte spätestens nach der Akteneinsicht vom 6. Juni 2008 intervenieren müssen, wenn er die UPK bzw. Dr. A._ als befangen betrachtet hätte. Dies habe er erst nach Bekanntgabe des für den Beschwerdeführer ungünstigen Gutachtens vom 28. August 2008 getan (Urteil, S. 4 f.).
1.2.2 Der Befangenheitsvorwurf ist gemäss Vorinstanz auch inhaltlich unbegründet. Dr. A._ sei beim Gutachten 2006 noch nicht Facharzt gewesen, weshalb er dieses nicht eigenverantwortlich habe erstellen können. Dr. B._ sei damals sein Vorgesetzter gewesen, weshalb er das Gutachten 2006 inhaltlich mitverantwortet habe. Beim Gutachten 2008 sei Dr. B._ hingegen nicht mehr beteiligt gewesen, da Dr. A._ zwischenzeitlich zum Oberarzt aufgestiegen sei. Das Gutachten 2008 habe lediglich Prof. E._ mitunterschrieben. Dieser sei es auch gewesen, der Dr. A._ nach der Krisensitzung Weisungen erteilt hätte, wovon Dr. B._ jedoch keine Kenntnis gehabt habe. Eine Befangenheit von Dr. A._ sei aufgrund seiner Stellung innerhalb der Klinik und als ehemaliger Untergebener von Dr. B._ zu verneinen. Eine solche ergebe sich auch nicht aufgrund seiner Teilnahme an der Krisensitzung vom 11. Dezember 2007. Dort sei lediglich für künftige Fälle abgeklärt worden, ob Anordnungen getroffen worden seien, die sich nachträglich als falsch erwiesen hätten. Es sei nicht ersichtlich, inwiefern Dr. A._ dadurch in irgendeiner Weise beeinflusst worden wäre (Urteil, S. 5 f.).
Zwischen Dr. D._ und Dr. B._ habe im Rahmen der Behandlung des Beschwerdeführers Kontakt bestanden. Als "Supervisor" sei Dr. B._ jedoch eigenen Angaben zufolge nicht direkt in die Therapie involviert gewesen. Gemäss Vorinstanz ist es trotzdem heikel, dass Dr. B._ die Gutachten in seiner Stellung als Sachverständiger vor der ersten Instanz erläutert habe. Ob deshalb eine Befangenheit bestehe, könne jedoch offenbleiben, da das Ergänzungsgutachten des FPD vom 29. Oktober 2010 einen allfälligen Mangel heile (Urteil, S. 5 f.).
1.3 Nach <ref-law> und Art. 6 Ziff. 1 EMRK hat jede Person Anspruch darauf, dass ihre Sache von einem unabhängigen und unparteiischen Richter ohne Einwirken sachfremder Umstände entschieden wird. Nach der Rechtsprechung gelten für Sachverständige grundsätzlich die gleichen Ausstands- und Ablehnungsgründe, wie sie für Richter vorgesehen sind. Da sie nicht dem Gericht angehören, richten sich die Anforderungen zwar nicht nach <ref-law>, sondern nach <ref-law>. Hinsichtlich der Unparteilichkeit und Unbefangenheit kommt <ref-law> indessen ein mit <ref-law> weitgehend übereinstimmender Gehalt zu (vgl. die Übersicht über die jüngere Rechtsprechung im Urteil 1B_188/2011 vom 1. Juni 2011 E. 3.2). Danach ist Befangenheit anzunehmen, wenn Umstände vorliegen, die geeignet sind, Misstrauen in die Unparteilichkeit zu erwecken. Bei dessen Beurteilung ist nicht auf das subjektive Empfinden einer Partei abzustellen. Das Misstrauen in die Unvoreingenommenheit muss vielmehr in objektiver Weise begründet erscheinen. Bei der Befangenheit handelt es sich allerdings um einen inneren Zustand, der nur schwer bewiesen werden kann. Es braucht für die Ablehnung nicht nachgewiesen zu werden, dass die sachverständige Person tatsächlich befangen ist. Es genügt vielmehr, wenn Umstände vorliegen, die objektiv den Anschein der Befangenheit zu begründen vermögen (<ref-ruling> E. 2.1; <ref-ruling> E. 3.2.1; <ref-ruling> E. 3.1; je mit Hinweisen). Umstände, welche den Anschein der Befangenheit begründen, können insbesondere im Verhalten der betroffenen Person oder in äusseren Gegebenheiten funktioneller und organisatorischer Natur begründet sein. Auch ein persönliches Interesse am Verfahrensausgang sowie persönliche oder wirtschaftliche Beziehungen zu einem Verfahrensbeteiligten sind bedeutsam (vgl. die Hinweise im Urteil 1B_188/2011 vom 1. Juni 2011 E. 3.2).
1.4 Nach der Rechtsprechung sind Ablehnungsgründe sofort geltend zu machen, wenn der Betroffene von diesen Kenntnis erlangt hat (<ref-ruling> E. 4.3.1 mit Hinweisen). Im vorliegenden Fall stellt sich die Frage der Verspätung von Ablehnungsgründen allerdings nicht, weil <ref-law> über die unabhängige sachverständige Begutachtung einen gesetzlichen Unvereinbarkeitsgrund vorsieht, der von Amtes wegen zu berücksichtigen ist. Hat der Täter nach dieser Bestimmung eine Tat im Sinne von <ref-law> begangen (so etwa einen Mord, eine vorsätzliche Tötung oder eine schwere Körperverletzung), ist die Begutachtung durch einen Sachverständigen vorzunehmen, der den Täter weder behandelt noch in anderer Weise betreut hat.
1.5 Gemäss den vorinstanzlichen Sachverhaltsfeststellungen erstellte Dr. A._ die beiden Gutachten über den Beschwerdeführer aus den Jahren 2006 und 2008. Beim ersten Gutachten wirkte Dr. B._ als direkter Vorgesetzter mit, während Dr. A._ das zweite Gutachten in alleiniger Verantwortung erstellte. Beide Gutachten visierte ausserdem der damalige Klinikleiter, Prof. E._. Dr. A._ war zu keinem Zeitpunkt an der eigentlichen Behandlung des Beschwerdeführers beteiligt. Seine Teilnahme an der Krisensitzung vom 11. Dezember 2007, die als Folge der erneuten und schweren Delinquenz des Beschwerdeführers anberaumt wurde, führt nicht dazu, dass er diesen im Sinne von <ref-law> selber behandelt oder in anderer Weise betreut hätte. Die Protokollnotizen ergeben lediglich, dass Dr. A._ eine forensische Präsentation des Falles vorgenommen hatte (pag. 1124 der Vorakten).
1.6 Problematisch erscheint allerdings die Unabhängigkeit von Dr. B._, der die ambulante Massnahme des Beschwerdeführers durch Dr. D._ zumindest als "Supervisor" begleitet hatte. Zwischen den beiden Ärzten bestand im Rahmen der Massnahme denn auch Kontakt. Da Dr. A._ das erste Gutachten noch zusammen mit seinem Vorgesetzten Dr. B._ erstellt hatte und erst nach seiner Beförderung zum Oberarzt eine eigenständige Stellung einnahm, kann bei Dr. B._ der Anschein von Befangenheit nicht von vornherein ausgeschlossen werden.
Die Vorinstanz bezeichnet die Stellung von Dr. B._ als Sachverständiger als "heikel", lässt die Frage seiner Befangenheit jedoch offen, da ein allfälliger Mangel durch das Ergänzungsgutachten geheilt werde. Die Vorinstanz vermengt dabei die beiden Fragen, ob einerseits ein Gutachten im Ergebnis schlüssig ist und andererseits der Autor oder Mitautor des Gutachtens unabhängig ist.
1.7 Erscheint dem Gericht die Schlüssigkeit eines Gutachtens in wesentlichen Punkten zweifelhaft, hat es nötigenfalls ergänzende Beweise zur Klärung zu erheben. Auf eine nicht schlüssige Expertise abzustellen bzw. auf die gebotenen zusätzlichen Beweiserhebungen zu verzichten, kann gegen das Verbot willkürlicher Beweiswürdigung verstossen (<ref-ruling> E. 3.2; <ref-ruling> E. 5.4.2; je mit Hinweisen). Ein Zweit- oder Ergänzungsgutachten ist einzuholen, wenn der gutachterliche Befund nicht genügt. Welche Art von Gutachten anzuordnen ist, ist Ermessensfrage. Ein Zweitgutachten steht im Vordergrund, wenn das Gericht ein bestehendes Gutachten für klar unzureichend und kaum verwertbar erachtet (Urteil 6B_650/2011 vom 10. April 2012 E. 3.1 mit Hinweisen).
1.8 Der Beschwerdeführer stellt Inhalt und Qualität der Gutachten nicht in Frage (Beschwerde, S. 12). Er führt zu Recht aus, dass ein Ergänzungsgutachten die Befangenheit bzw. den Anschein einer Befangenheit des Erstgutachters nicht heilen kann. Sein Befangenheitsvorwurf gegenüber Dr. B._, der als Sachverständiger im Rahmen der erstinstanzlichen Hauptverhandlung geamtet hat, ist begründet. Dieser war - wie oben erwähnt - als Supervisor an der Durchführung der ambulanten Massnahme mit Dr. D._ beteiligt, verfasste das Gutachten 2006 zusammen mit Dr. A._ und war während der ganzen Zeit dessen Vorgesetzter. Dass Dr. A._ nach Erlangung des Facharzttitels eine gewisse Selbständigkeit zugekommen ist und das Gutachten 2008 eigenverantwortlich betreut hat, kann an der Befangenheit von Dr. B._ nichts ändern. Die Vorinstanz hat zu Unrecht dessen Befangenheit bzw. zumindest den Anschein der Befangenheit verneint und verletzt dadurch den Anspruch des Beschwerdeführers auf einen unabhängigen Sachverständigen (<ref-law> und Art. 6 Ziff. 1 EMRK). Sie verletzt ebenfalls <ref-law>, der eine unabhängige sachverständige Begutachtung verlangt.
Von der Aufhebung des Urteils des Appellationsgerichts des Kantons Basel-Stadt vom 23. August 2011 ist gleichwohl abzusehen. Weder der Beschwerdeführer noch die Verfasserin des Ergänzungsgutachtens üben inhaltliche Kritik an den beiden Gutachten von Dr. A._. Der Beschwerdeführer bezeichnet das Gutachten 2008 als schlüssig und überzeugend, weshalb die Vorinstanz zu Recht darauf abgestellt hat. Der Beschwerdeführer bringt nicht vor, die sachverständige Erläuterung von Dr. B._ hätte das Gutachten 2008 in Frage gestellt oder die beiden kantonalen Instanzen in ihrer Entscheidfindung beeinflusst. Dies ist auch nicht ersichtlich. Mit einer Wiederholung der erstinstanzlichen Hauptverhandlung und der Bestellung eines unbefangenen Sachverständigen wäre daher nichts gewonnen.
2. Die Beschwerde ist im Sinne der Erwägungen abzuweisen. Da der Beschwerdeführer zu Recht die Befangenheit von Dr. B._ beanstandet hat, werden keine Gerichtskosten erhoben (<ref-law>). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen. Der Rechtsvertreter des Beschwerdeführers ist aus der Bundesgerichtskasse angemessen zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird im Sinne der Erwägungen abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen. Dem Beschwerdeführer wird Rechtsanwalt Dr. Christian von Wartburg als unentgeltlicher Rechtsbeistand beigegeben.
3. Es werden keine Gerichtskosten erhoben.
4. Dem Rechtsvertreter des Beschwerdeführers wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- aus der Bundesgerichtskasse ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 27. September 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Schneider
Der Gerichtsschreiber: Keller