Sachverhalt:
A. Der als Grenzgänger in Basel arbeitende X._ fuhr am 22. Februar 2008 um ca. 06.15 Uhr von seinem elsässischen Wohnort Hagenthal-le-Bas Richtung Basel. Auf der Strecke zwischen Hagenthal und Hégenheim, die mit einer Höchstgeschwindigkeit von 90 km/h signalisiert ist, reduzierte er seine Fahrgeschwindigkeit stark, weil er aufgrund der Wetterverhältnisse Glatteis befürchtete. Der nachfolgende Fahrzeuglenker A._ überholte ihn, worauf X._ den Scheinwerfer, eventuell zusätzlich die Hupe, betätigte und sehr nahe auf das überholende Fahrzeug aufschloss. Als dieses anhielt, überholte ihn X._. A._ folgte ihm daraufhin lichthupend. In Hégenheim fuhr X._ zunächst sehr langsam im Slalom, später zügiger Richtung Grenzübergang Hegenheimerstrasse. A._ folgte X._ weiterhin und wollte ihn zur Rede stellen. Dieser versuchte, sich im Bereich der Kreuzung Bündner-/Sierenzerstrasse mit seinem Fahrzeug zu verstecken. Dies gelang ihm nicht. A._ hielt in einer Entfernung von rund 20 Metern zum Wagen von X._ an. Beide stiegen aus ihren Wagen aus. Nach einem kurzen Handgemenge stiess X._ A._ einen Dolch in den Lendenbereich. Dieser wehrte sich weiter und schlug ihm mit der Faust gegen die rechte obere Kopfhälfte. X._ fügte A._ in der Folge eine Schnittwunde an der linken Seite des Kopfes zu und ergriff danach die Flucht.
B. Das Strafgericht Basel-Stadt verurteilte X._ am 16. September 2009 wegen versuchter vorsätzlicher Tötung und Widerhandlung gegen das Waffengesetz zu einer Freiheitsstrafe von 3 1⁄2 Jahren, zu Schadenersatz von Fr. 3'189.-- sowie zu Genugtuungszahlungen von insgesamt Fr. 13'500.--, jeweils zuzüglich Zins.
Die von X._ erhobene Appellation hiess das Appellationsgericht Basel-Stadt am 20. Januar 2012 teilweise gut. Es verurteilte ihn wegen versuchter vorsätzlicher Tötung und Widerhandlung gegen das Waffengesetz zu einer Freiheitsstrafe von 3 Jahren, davon 24 Monate bedingt aufgeschoben, bei einer Probezeit von zwei Jahren. Im Übrigen bestätigte es das erstinstanzliche Urteil.
C. X._ erhebt Beschwerde in Strafsachen. Er beantragt, das Urteil des Appellationsgerichts Basel-Stadt vom 20. Januar 2012 sei aufzuheben und im Sinne der bundesgerichtlichen Erwägungen zur neuen Entscheidung an die Vorinstanz zurückzuweisen. X._ verlangt ein Replikrecht zur Stellungnahme des Beschwerdegegners. Ausserdem sei der Beschwerde aufschiebende Wirkung im Zivilpunkt zu gewähren.

Erwägungen:
1. 1.1 Der Beschwerdeführer rügt auf mehreren Seiten seiner Beschwerde, die Vorinstanz habe aktenwidrig festgestellt, dass er sein Auto in der Bündnerstrasse, einige Meter vor der querenden Sierenzerstrasse, abgestellt habe (Beschwerde, S. 4-13). Die Vorinstanz verletze den Grundsatz "in dubio pro reo". Es seien in den Akten Beweise vorhanden, dass er sein Auto weiter vorne im Kreuzungsbereich der beiden Strassen abgestellt habe. Ebenso verletze die Vorinstanz seinen Anspruch auf rechtliches Gehör, indem sie ihrem Urteil Behauptungen zur Sichtmöglichkeit im Rückspiegel zugrunde lege, die nie Gegenstand des Beweisverfahrens gewesen seien (Beschwerde, S. 12 f.).
Der Beschwerdeführer beanstandet ferner, dass die Vorinstanz den Ablauf der Auseinandersetzung zwischen ihm und dem Beschwerdegegner 2 falsch festgestellt habe (Beschwerde, S. 18).
1.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zu Grunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG; Art. 105 Abs. 2 BGG). Offensichtlich unrichtig im Sinne von Art. 97 Abs. 1 BGG ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 4.2 mit Hinweisen; zum Begriff der Willkür <ref-ruling> E. 7.1; <ref-ruling> E. 4.2; je mit Hinweisen). Eine entsprechende Rüge muss klar und substantiiert begründet werden (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; <ref-ruling> E. 4.2.3; <ref-ruling> E. 1.3.1; je mit Hinweisen). Der Beschwerdeführer, der die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss mithin detailliert aufzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruhen. In der Beschwerde muss im Einzelnen dargelegt werden, inwiefern der angefochtene Entscheid an einem qualifizierten und offensichtlichen Mangel leidet. Auf eine rein appellatorische Kritik tritt das Bundesgericht nicht ein (<ref-ruling> E. 4.2.3; <ref-ruling> E. 2.8; je mit Hinweisen).
1.3 Der Beschwerdeführer legt nicht dar, inwiefern die Behebung des von ihm behaupteten Mangels der vorinstanzlichen Sachverhaltsfeststellung für den Ausgang des Verfahrens entscheidend sein kann. Er begnügt sich mit der Feststellung, für die Vorinstanz sei zur Beurteilung einer Notwehrlage massgebend, wo er und der Beschwerdegegner 2 ihre Fahrzeuge angehalten und wo sie den Konflikt ausgetragen hätten. Die Vorinstanz führt in diesem Zusammenhang jedoch nur aus, dass diese Frage aus Sicht des Beschwerdeführers entscheidend sei (Urteil, S. 3). Auf seine im Übrigen appellatorischen Vorbringen zu den vorinstanzlichen Sachverhaltsfeststellungen ist nicht einzutreten.
2. 2.1 Der Beschwerdeführer rügt eine willkürliche Beweiswürdigung, da die Vorinstanz auf das offenkundig mangelhafte Gutachten vom 29. April 2008 abgestellt habe. Dieses sei weder schlüssig noch nachvollziehbar. Es gehe von einer Stichwunde im Bereich der linken Körperflanke von 3 cm aus, obwohl die zugehörigen Abbildungen eine knapp über 2 cm lange Einstichwunde zeigten. Dies sei anhand des abgebildeten Massstabs deutlich sichtbar. Die Vorinstanz leite aus der zu gross bemessenen Einstichwunde ab, dass diese grösser als die Messerklinge an ihrer breitesten Stelle sei und der Beschwerdeführer wuchtig und tief in den Körper eingestochen habe. Tatsächlich sei die Wunde aber genau gleich gross wie das Messer gewesen. Dieses habe auch deshalb nicht tief eindringen können, weil der Beschwerdegegner 2 den Einstich zunächst gar nicht gespürt habe. Das Gutachten begründe mit keinem Wort, weshalb es entgegen dem ersten Gutachten vom 27. Februar 2008 von einer eröffneten Bauchhöhle ausgehe. Die Gerichtsgutachterin erkläre dies mit dem Umstand, dass der untersuchende Chirurg andernfalls einen Stichkanal in der Muskulatur hätte näher beschreiben und dokumentieren müssen. Damit bestehen nach Auffassung des Beschwerdeführers jedoch nicht überwindbare Zweifel an dieser Sachverhaltsversion, weshalb in dubio pro reo von der günstigeren Variante hätte ausgegangen werden müssen (Beschwerde, S. 13-16).
2.2 Die Vorinstanz erwägt, der Beschwerdeführer habe eigenen Angaben zufolge nach seinem Messer gegriffen, als der Beschwerdegegner 2 ausgestiegen und auf ihn zugekommen sei. Er sei diesem entgegen gegangen, um die Konfrontation zu suchen. Es verstehe sich von selbst, dass ein Dolchmesser mit einer 11 cm langen und 2 cm breiten Klinge generell geeignet sei, tief genug in den menschlichen Körper einzudringen, um lebenswichtige Organe und Gefässe zu treffen. Ein Stich in den Rücken sei nie das Ergebnis einer zufälligen Bewegung. Ihm liege stets ein willentlicher Entschluss zugrunde. Es lasse sich zwar nicht mehr feststellen, wie tief der Beschwerdeführer den Dolch in den Rücken gestossen habe. Damit die Waffe aber überhaupt durch die Kleider in den Leib habe eindringen können, habe er weit ausholen und den Stich mit Schwung ausführen müssen. Für die Wucht sprächen auch die Verletzungen des Beschwerdegegners 2. Die Blutung im Raum hinter dem Bauchfell weise gemäss Gutachterin (im Gegensatz zum Privatgutachter) darauf hin, dass die Tatwaffe in die Bauchhöhle eingedrungen sei (Urteil, S. 8 ff.).
2.3 Die Vorbringen des Beschwerdeführers sind unbegründet. Das von ihm als "offenkundig mangelhaft" bezeichnete Gutachten vom 29. April 2008 ist nicht zu beanstanden. Zwar beantwortet es die Frage nach der Länge des Stichs unrichtig. Es beziffert diesen mit 3 cm (pag. 164 der Vorakten), während die Befunde der rechtsmedizinischen Untersuchung korrekt von 2 cm ausgehen (pag. 163 der Vorakten), was sich aus den beiliegenden Fotos der Wunde ohne weiteres ergibt (pag. 167 der Vorakten). Das Gutachten begründet entgegen dem Beschwerdeführer auch, weshalb der Stich bis in die Körperhöhle vorgedrungen ist (pag. 164 f. der Vorakten). Im ersten, fünf Tage nach der Tat erstellten, Gutachten vom 27. Februar 2008 konnte diese Frage noch nicht abschliessend beantwortet werden, da zu diesem Zeitpunkt noch keine Informationen aus dem behandelnden Spital vorlagen.
Ob die vorinstanzliche Beweiswürdigung in der Sache zutreffend ist, kann das Bundesgericht nur unter dem beschränkten Blickwinkel der Willkür überprüfen. Es ist aus dieser Sicht nicht zu beanstanden, wenn die Vorinstanz auf das Gutachten vom 29. April 2008 abstellt und die abweichenden Ausführungen des Privatgutachters unberücksichtigt lässt. Die Vorinstanz übernimmt zwar die falsche Längenangabe der Einstichwunde von 3 cm. Sie begründet ihre Feststellungen zur Tiefe und Heftigkeit des Einstichs allerdings insbesondere damit, dass der Beschwerdeführer die (winterliche) Kleidung des Beschwerdegegners 2 durchstossen musste und eine Blutung im Raum hinter dem Bauchfell auf ein tiefes Eindringen in die Bauchhöhle schliessen lässt. Selbst wenn eine andere Lösung oder Würdigung vertretbar erscheint oder gar vorzuziehen wäre (<ref-ruling> E. 7.1; <ref-ruling> E. 7; <ref-ruling> E. 2.4; je mit Hinweisen), ist die vorinstanzliche Sachverhaltsfeststellung nicht willkürlich.
3. 3.1.1 Der Beschwerdeführer rügt eine fehlerhafte Rechtsanwendung. Die Vorinstanz habe die inkriminierte Handlung zu Unrecht als eventualvorsätzlich versuchte Tötung qualifiziert. Er beanstandet, die Vorinstanz habe wenig vergleichbare Präjudizien beigezogen und führt eigene Referenzen von Bundesgerichtsurteilen an. Diesen Entscheiden könne entnommen werden, dass die Klingenlänge, die Wucht und Lage des Stichs sowie der Verlauf des Stichkanals wesentlich seien, um die Tat als versuchte vorsätzliche Tötung oder als Körperverletzung zu qualifizieren. Das Bundesgericht habe eine solche nur bejaht, wenn der Stich mit einem Messer von rund 10 cm Klingenlänge gegen das Körperinnere geführt worden sei. Zudem sei es unerlässlich, den Verlauf des Stichkanals zu kennen, um das dem Täter bekannte Risiko der Tatbestandsverwirklichung abschätzen zu können. Vorliegend sei lediglich die Länge der Messerklinge bekannt, während die Länge des Stichkanals und die Wucht des Einstichs nicht bestimmbar seien. Es sei daher unzulässig, eine versuchte vorsätzliche Tötung anzunehmen. Die Verletzung am Kopf des Beschwerdegegners 2 sei nicht lebensgefährlich gewesen, da der kritische Schockindex-Wert nicht erreicht worden sei und sich der Blutverlust in Grenzen gehalten habe. Die Vorinstanz stelle hingegen einen abweichenden Sachverhalt fest, obwohl es nur aus triftigen Gründen von den Erkenntnissen des rechtsmedizinischen Gutachtens abweichen dürfte (Beschwerde S. 20-24).
3.1.2 Der Beschwerdeführer verneint den (Eventual-)Vorsatz auch deshalb, weil er die Konfrontation mit dem Beschwerdegegner 2 nicht gesucht habe. Er habe dieser vielmehr ausweichen und sich verstecken wollen, habe wegen der Baustelle im Bereich der Bündner-/Sierenzerstrasse aber nicht mehr weiterfahren können. Er habe sich in der Folge der Konfrontation gestellt, weil er sie wegen äusserer Umstände nicht mehr habe vermeiden können (Beschwerde, S. 24 f.).
Der Beschwerdeführer widerspricht der vorinstanzlichen Erwägung, dass ein Stich in den Rücken kein zufälliges Ereignis darstelle und ihm immer ein willentlicher Entschluss zugrundeliege. Er habe subjektiv nicht davon ausgehen müssen, dass sein Handeln zu einer objektiv lebensbedrohlichen Verletzung hätte führen können. Dies gelte insbesondere, wenn der Stichkanal und die Tiefe der Wunde unbekannt seien (Beschwerde S. 25-29).
3.2 Die Vorinstanz bejaht die Eignung der Tatwaffe, um tief in den menschlichen Körper einzudringen und damit lebenswichtige Organe und Gefässe zu treffen (vgl. oben E. 2.3). Sie führt zudem aus, dass eine zufällige Bewegung nicht zu einem Stich in den Rücken führen kann, sondern dafür ein willentlicher Entschluss vorliegen müsse. Da die Bauchhöhle dicht mit Organen bepackt sei, habe es gemäss der Gutachterin nur vom Schicksal abgehangen, keines dieser Organe zu treffen. Auch der Privatgutachter habe bestätigt, dass die Waffe nicht mehr steuerbar sei, wenn sie die Haut durchdrungen habe. Es sei lediglich dem Zufall zu verdanken, dass der Beschwerdeführer mit seinem Stich keine lebenswichtigen Organe und Blutgefässe getroffen habe. Selbst wenn man zu seinen Gunsten annehme, dass der Stichkanal an der Oberfläche in Richtung Wirbelsäule verlaufen sei, könne ihn das nicht entlasten. Da er den Rücken während der Auseinandersetzung nicht habe einsehen können und sich beide bewegt hätten, sei er nicht in der Lage gewesen, den Stich gezielt an einem ungefährlichen Ort auszuführen. Zudem habe ihm als Nichtmediziner das diesbezügliche Wissen gefehlt. Der Beschwerdeführer habe auch nach dem Stich nicht vom Beschwerdegegner 2 abgelassen, sondern diesem gezielt eine 8 cm lange Kopfschwartenwunde zugefügt. Diese zeuge ebenfalls von der Heftigkeit seines Angriffs. Der Schwartenriss habe einen grossen Blutverlust zur Folge gehabt, wobei der Schockindex bei 0,95 gelegen, und damit einen Wert nahe beim lebensbedrohlichen Blutverlust (ab Schockindex 1,0) erreicht habe. Mit seinen unkontrollierten, wuchtigen Stichen in Rücken und Kopf des Beschwerdegegners 2 in die Nähe lebenswichtiger Organe und Gefässe habe er dessen Tod zumindest in Kauf genommen (Urteil, S. 8 ff.).
3.3 Eventualvorsatz nach Art. 12 Abs. 2 StGB liegt vor, wenn der Täter den Eintritt des Erfolgs beziehungsweise die Tatbestandsverwirklichung für möglich hält, aber dennoch handelt, weil er den Erfolg für den Fall seines Eintritts in Kauf nimmt, sich mit ihm abfindet, mag er ihm auch unerwünscht sein. Der Richter darf vom Wissen des Täters auf den Willen schliessen, wenn sich diesem der Eintritt des Erfolgs als so wahrscheinlich aufdrängte, dass die Bereitschaft, ihn als Folge hinzunehmen, vernünftigerweise nur als Inkaufnahme des Erfolgs ausgelegt werden kann (<ref-ruling> E. 4.2.3 mit Hinweis).
Wie die Vorinstanz ausführlich und willkürfrei darlegt, führte der Beschwerdeführer die inkriminierten Messerstiche mit Wucht in den Rücken sowie in den Kopf des Beschwerdegegners 2 aus. Dass er dabei keine lebenswichtigen Organe und Blutgefässe getroffen hat und dieser nicht verblutet ist, war einzig dem Zufall zu verdanken. Während der Konfrontation waren die beiden Kontrahenten in Bewegung. Die Tathandlung fand im Februar um ca. 06.30 Uhr in dunkler Nacht statt. Der Beschwerdeführer stach dem Beschwerdegegner 2 von vorne in den Rücken, womit er keine Möglichkeit hatte - selbst wenn er das notwendige Wissen gehabt hätte - zielgenau zuzustechen, um allenfalls lebenswichtige Organe zu verschonen. Die Vorinstanz erwähnt in diesem Zusammenhang zutreffend, dass ihn daher auch eine geringe Einstichtiefe nicht entlasten würde. Da er trotzdem zweimal in den Kopf und den Rücken des Beschwerdegegners 2 stach, nahm er dessen Tod zumindest in Kauf. Die Vorinstanz verletzt kein Bundesrecht, indem sie eine eventualvorsätzlich versuchte Tötung bejaht.
4. 4.1 Der Beschwerdeführer macht als Rechtfertigungsgrund geltend, der Beschwerdegegner 2 habe ihn während einer halben Stunde über eine grössere Distanz verfolgt, bis er sich in eine Sackgasse manövriert habe und der Konfrontation nicht mehr habe ausweichen können. Die Vorinstanz habe die Situation fälschlicherweise als nicht bedrohlich eingestuft. Es könne ihm aber nicht verargt werden, dass er sich unter diesen Umständen bedroht gefühlt habe. Der Sachverhaltsirrtum eines unmittelbar bevorstehenden Angriffs sei nicht vermeidbar gewesen. Als körperlich Unterlegener sei er ohne weiteres berechtigt gewesen, sich zu seiner Verteidigung zu bewaffnen. Die Vorinstanz gehe zu Unrecht davon aus, dass er nur unwesentlich älter und zudem grösser als der Beschwerdegegner 2 sei. Zu welcher Beurteilung die Vorinstanz bei korrekten Grössen- und Gewichtsverhältnissen der Beteiligten gelangt wäre, könne nur bei einer Neubeurteilung des Falles beantwortet werden. Er sei aufgrund der Notwehrsituation, allenfalls im Rahmen eines Sachverhaltsirrtums, höchstens wegen fahrlässiger Tatbegehung zu bestrafen (Beschwerde, S. 16 f. und S. 30 f.).
4.2 Die Vorinstanz erwägt ausführlich, weshalb der Beschwerdeführer keiner Notwehrsituation unterlag und ein Sachverhaltsirrtum ausgeschlossen werden kann (Urteil, S. 12-15). Auf die zutreffenden vorinstanzlichen Erwägungen kann verwiesen werden. Im Moment als der Beschwerdegegner 2 ausstieg und auf das Auto des Beschwerdeführers zustrebte, war die Situation nicht so bedrohlich, dass er einen Dolch hätte behändigen und ohne Vorwarnung oder visuelle Drohung hätte einsetzen dürfen. Die Vorinstanz hat Rechtfertigungsgründe zu Recht verneint. Dies gilt auch für den Fall, dass man der Auffassung des Beschwerdeführers folgt, wonach er dem Beschwerdegegner 2 körperlich unterlegen war und die Vorinstanz dies übergangen beziehungsweise zu wenig würdigte.
5. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang trägt der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens (Art. 66 Abs. 1 Satz 1 BGG). Mit dem Entscheid in der Sache selbst wird der Antrag des Beschwerdeführers um aufschiebende Wirkung im Zivilpunkt gegenstandslos. Dasselbe gilt für seinen Verfahrensantrag zum Replikrecht, da keine Vernehmlassungen eingeholt wurden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 11. Oktober 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Keller