Sachverhalt: A. Am 24. Juni 2007 hielt X._ im Verlaufe einer vorerst verbalen und später tätlichen Auseinandersetzung eine Faustfeuerwaffe mit ausgestrecktem Arm aus einer Entfernung von mindestens einem Meter gegen seine frühere Freundin A.A._ und drückte ab. Sie erlitt eine Durchschussverletzung an der linken Schulter. In der Folge richtete er die Waffe gegen deren Schwester B.A._, ohne jedoch den Abzug zu betätigen. B. Das Obergericht des Kantons Zürich sprach X._ mit Urteil vom 14. Oktober 2011 zweitinstanzlich der versuchten vorsätzlichen Tötung schuldig. Gleichzeitig stellte es fest, dass der erstinstanzliche Entscheid des Bezirksgerichts Zürich vom 9. März 2011 insbesondere betreffend den Schuldspruch der einfachen Körperverletzung, der mehrfachen Drohung, der Widerhandlung gegen das Bundesgesetz vom 20. Juni 1997 über Waffen, Waffenzubehör und Munition (Waffengesetz, WG; SR 514.54) sowie betreffend die Zivilforderungen von A.A._ und B.A._ in Rechtskraft erwachsen war. Das Obergericht verurteilte X._ zu einer Freiheitsstrafe von 10 1⁄2 Jahren unter Anrechnung der ausgestandenen Untersuchungs- und Sicherheitshaft von 983 Tagen. C. X._ führt Beschwerde ans Bundesgericht. Er beantragt, die Sache sei zur Wiederholung des Berufungsverfahrens an die Vorinstanz zurückzuweisen. Eventualiter sei er vom Vorwurf der versuchten vorsätzlichen Tötung freizusprechen und wegen einfacher Körperverletzung und den bereits rechtskräftigen Schuldsprüchen zu einer Freiheitsstrafe von zwei Jahren zu verurteilen. Subeventualiter sei er wegen versuchter vorsätzlicher Tötung mit einer Freiheitsstrafe von höchstens fünf Jahren zu bestrafen. Zudem ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. D. Das Obergericht des Kantons Zürich hat auf Vernehmlassung verzichtet. Die Oberstaatsanwaltschaft des Kantons Zürich beantragt die Abweisung der Beschwerde und lässt sich im Übrigen nicht vernehmen.