Sachverhalt: A. Am 13. Februar 2009, eventuell am 14./15. Februar 2009, hütete X._ in der gemeinsamen Familienwohnung seine am 29. Januar 2009 geborene Tochter A.Y._. Als der Säugling schrie, packte er ihn mit beiden Händen um den Brustkorb und drückte während 5 bis 10 Sekunden derart stark zu, dass rechts die 6. und 9. Rippe und links die Rippen 7 bis 9 brachen. Als A.Y._ weiter schrie, setzte sich X._ mit ihr auf das Sofa, packte sie hinten am Hals am Kleidchen und knüllte dieses an der Aussparung so zusammen, dass das Kind nicht mehr atmen konnte. Während er seine Tochter auf diese Weise längere Zeit würgte, schaute er zum Fernseher, der ausgeschaltet war. Als A.Y._ zu schreien aufhörte, liess er von ihr ab. Sie war blau im Gesicht. Er brachte sie zurück in ihr Bettchen. A.Y._ erlitt durch das länger andauernde Würgen neben ausgeprägten Hautläsionen am Hals aufgrund der Unterbrechung der Sauerstoffzufuhr eine Beeinträchtigung der Hirndurchblutung bei unmittelbarer Lebensgefahr. Im Rahmen des gleichen Vorgangs wirkte X._ weiter auf A.Y._ ein, indem er an ihr zerrte, sie schlug, stiess und schüttelte. Sie erlitt einen Bluterguss zwischen den harten und weichen Hirnhäuten sowie eine Hirnprellung. Ausserdem verabreichte er ihr einen Schoppen mit zu heisser Milch, so dass sich der Säugling im inneren und äusseren Mundbereich verbrühte und mit einer Magensonde ernährt werden musste. Vermutlich ein bis zwei Tage später, als X._ A.Y._ unter erheblicher Gewaltanwendung grob auszog und brutal an den Armen zerrte, um sie zu waschen, brach er ihr beide Oberarmknochen. B. Das Bezirksgericht Bülach sprach X._ am 11. Mai 2011 des versuchten Mordes und der mehrfachen qualifizierten einfachen Körperverletzung schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von 8 Jahren unter Anrechnung der Untersuchungshaft und des vorzeitigen Strafvollzugs und ordnete eine ambulante Massnahme an. Gegen dieses Urteil erhob die Staatsanwaltschaft des Kantons Zürich Berufung. X._ legte Anschlussberufung ein. Das Obergericht des Kantons Zürich sprach X._ am 29. Februar 2012 der versuchten Tötung und der mehrfachen qualifizierten einfachen Körperverletzung schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von 11 Jahren unter Anrechnung der Untersuchungshaft und des vorzeitigen Strafvollzugs. Im Übrigen bestätigte es das erstinstanzliche Urteil. C. Mit Beschwerde in Strafsachen beantragt die Oberstaatsanwaltschaft des Kantons Zürich, das Urteil des Obergerichts sei in Bezug auf den Schuldspruch der versuchten Tötung aufzuheben, und die Sache sei zur Verurteilung von X._ wegen versuchten Mordes und zur neuen Strafzumessung an die Vorinstanz zurückzuweisen. D. Das Obergericht des Kantons Zürich verzichtet auf eine Stellungnahme zur Beschwerde. X._ beantragt, es sei der obergerichtliche Schuldspruch wegen versuchter eventualvorsätzlicher Tötung zu bestätigen, und er sei zu einer höchstens vierjährigen Freiheitsstrafe (unter Anrechnung der Haftzeiten und des vorzeitigen Strafantritts) zu verurteilen. Überdies sei ihm die unentgeltliche Rechtspflege zu gewähren. B.Y._, die Mutter von A.Y._ und Partnerin von X._, reicht einen "Geschädigtenbericht" ein.