Sachverhalt:
A. Das Strafgericht Basel-Stadt sprach X._ mit Urteil vom 3. November 2009 der versuchten vorsätzlichen Tötung schuldig. Es bestrafte ihn mit einer Freiheitsstrafe von 6 1⁄2 Jahren.
Auf Appellation von X._ und des Opfers bestätigte das Appellationsgericht des Kantons Basel-Stadt am 14. Januar 2011 den Schuldspruch und setzte die Freiheitsstrafe auf 5 1⁄2 Jahre fest.
B. X._ reichte am 25. Mai 2011 bei der Staatsanwaltschaft Basel-Stadt ein Revisionsgesuch betreffend die Verurteilung vom 14. Januar 2011 ein. Das Appellationsgericht des Kantons Basel-Stadt trat am 20. September 2011 auf das Gesuch nicht ein.
Am 10. Juni 2012 stellte X._ wiederum ein Revisionsgesuch, auf welches das Appellationsgericht am 22. Juni 2012 nicht eintrat.
C. X._ führt Beschwerde in Strafsachen. Er beantragt, der Entscheid des Appellationsgerichts vom 22. Juni 2012 sei aufzuheben. Auf das Revisionsgesuch sei einzutreten, eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
D. Das Appellationsgericht des Kantons Basel-Stadt beantragt, die Beschwerde sei gutzuheissen. Die Staatsanwaltschaft des Kantons Basel-Stadt beantragt die Abweisung der Beschwerde.

Erwägungen:
1. Der Beschwerdeführer verlangt wie bereits im kantonalen Verfahren, es sei A._ vorsorglich zum Vorfall vom 13. März 2009 zu befragen. Er gehe davon aus, dass der Zeuge aus der Schweiz ausreise, weshalb sich eine vorsorgliche Einvernahme aufdränge (Beschwerde S. 2). Die Notwendigkeit einer solchen vorsorglichen Massnahme (<ref-law>) ist grundsätzlich durch den Gesuchsteller darzutun. Die vom Beschwerdeführer vermutete Wegweisung erschöpft sich in einer blossen und nicht substanziierten Behauptung. Zudem bleibt unerwähnt, in welches Land A._ ausgeschafft werden soll und inwieweit eine (rechtshilfeweise) Einvernahme nicht möglich ist. Darauf ist nicht einzutreten.
2. 2.1 Der Beschwerdeführer rügt eine Verletzung von <ref-law>. Die Vorsitzende im Appellationsverfahren betreffend das Urteil des Strafgerichts Basel-Stadt sei B._ gewesen. Die gleiche Richterin habe auch im vorinstanzlichen Revisionsverfahren mitgewirkt (Beschwerde S. 8).
2.2 Nach <ref-law> können Mitglieder des Berufungsgerichts nicht im gleichen Fall als Revisionsrichter tätig sein. Damit wird praktisch der Ausstandsgrund von <ref-law> wiederholt (ANDREAS KELLER, in: Kommentar zur Schweizerischen Strafprozessordnung, 2010, N. 4 zu <ref-law>). Die Rechtsprechung zu <ref-law> und Art. 6 Abs. 1 EMRK schliesst zwar nicht aus, dass der Berufungsrichter in der gleichen Sache als Revisionsinstanz amtet (<ref-ruling> E. 2b S. 161; Urteil 1B_96/2009 vom 11. August 2009 E. 2; je mit Hinweisen). Gleichwohl soll nach der Regelung der Schweizerischen Strafprozessordnung nicht das gleiche Gericht über das Gesuch um Revision entscheiden wie dasjenige, welches den in Revision zu ziehenden Entscheid fällte. Der Gesetzgeber hat sich für eine strikte Trennung der verschiedenen Funktionen entschieden (HENZELIN/MAEDER, in: Commentaire romand, Code de procédure pénale suisse, 2011, N. 10 zu <ref-law>). Mit Art. 21 Abs. 2 und 3 StPO werden Bund und Kantone verpflichtet, eine solche Trennung auf geeignete Weise, wenn auch nur gerichtsintern, umzusetzen (Botschaft vom 21. Dezember 2005 zur Vereinheitlichung des Strafprozessrechts, BBl 2006 1140 Ziff. 2.2.1.3).
2.3 Im vorinstanzlichen Entscheid vom 22. Juni 2012, mit dem auf das Revisionsgesuch des Beschwerdeführers nicht eingetreten wurde, wirkten die Richterin B._ sowie die Gerichtsschreiberin C._ mit. Beide Gerichtspersonen waren Teil des Spruchkörpers, der mit Urteil vom 14. Januar 2011 den erstinstanzlichen Schuldspruch der versuchten vorsätzlichen Tötung bestätigte und auf eine Freiheitsstrafe von 5 1⁄2 Jahren erkannte (Verfahren AS.2009.403). Die Rüge des Beschwerdeführers ist begründet. Der Kanton Basel-Stadt hat Berufungs- und Beschwerdeinstanz im Appellationsgericht institutionell zusammengelegt (vgl. § 17, 18 und 22 des Gesetzes des Kantons Basel-Stadt vom 13. Oktober 2010 über die Einführung der Schweizerischen Strafprozessordnung [EG StPO; SG 257.100] sowie § 72 ff. des Gerichtsorganisationsgesetzes des Kantons Basel-Stadt vom 27. Juni 1895 [GOG; SG 154.100]). Diese Möglichkeit sieht die Schweizerische Strafprozessordnung vor (vgl. <ref-law>). Sicherzustellen ist aber, dass die Ausstandsregeln im Sinne von Art. 21 Abs. 2 und 3 StPO eingehalten werden können.
Der Beschwerdeführer gelangte mit Revisionsgesuch vom 10. Juni 2012 an die Vorinstanz. Diese zog die Verfahrensakten bei, verzichtete auf Stellungnahmen und fällte am 22. Juni 2012 den angefochtenen Nichteintretensentscheid. Am 3. Juli 2012 wurde er dem Beschwerdeführer schriftlich eröffnet. Dannzumal erfuhr der Beschwerdeführer, wer am Entscheid mitwirkte (Entscheid S. 1 und 6). Dass ihm die personelle Zusammensetzung der Vorinstanz (Richterin B._ und Gerichtsschreiberin C._) bereits zu einem früheren Zeitpunkt mitgeteilt wurde, geht aus den vorinstanzlichen Akten nicht hervor und wird auch in der Vernehmlassung nicht behauptet. Ebenso wenig musste der Beschwerdeführer damit rechnen, dass die Vorinstanz in gleicher Besetzung wie im früheren Revisionsverfahren (DG.2011.12) entscheiden würde. Er macht den Ausstandsgrund mit der Beschwerde ans Bundesgericht geltend. Die Rüge ist rechtzeitig erfolgt (vgl. MARKUS BOOG, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2011, N. 6 zu <ref-law>; Urteil des Kassationsgerichts des Kantons Zürich vom 10. Dezember 2002, in: ZR 102/2003 S. 157).
2.4 Indem die Richterin B._ und die Gerichtsschreiberin C._ über das Revisionsgesuch des Beschwerdeführers befanden, nachdem beide in der gleichen Sache im Appellationsverfahren AS.2009.403 mitgewirkt hatten, wird <ref-law> verletzt. Damit erübrigt es sich, die weiteren Rügen (Beschwerde S. 8 ff.) näher zu prüfen.
3. Die Beschwerde ist teilweise gutzuheissen. Soweit die vorsorgliche Zeugeneinvernahme verlangt wird, ist auf die Beschwerde nicht einzutreten. Der angefochtene Entscheid ist aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
Bei diesem Ausgang des Verfahrens rechtfertigt es sich, keine Kosten zu erheben. Der Kanton Basel-Stadt hat dem Rechtsvertreter des Beschwerdeführers eine Parteientschädigung von Fr. 2'000.-- zu bezahlen (Art. 68 Abs. 1 und 2 BGG). Damit wird das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 22. Juni 2012 aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen. Hinsichtlich der beantragten vorsorglichen Zeugeneinvernahme wird auf die Beschwerde nicht eingetreten.
2. Es werden keine Kosten erhoben.
3. Der Kanton Basel-Stadt hat den Rechtsvertreter des Beschwerdeführers, Advokat Markus Loher, für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Appellationsgerichtspräsidentin, schriftlich mitgeteilt.
Lausanne, 18. April 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Faga