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.

Erwägungen:
1. 1.1 Die Beschwerdeführerin wendet sich gegen die rechtliche Würdigung der Tat als vorsätzliche Tötung im Sinne von <ref-law>. Nach ihrer Auffassung ist das gewaltsame Einwirken des Beschwerdegegners auf den noch nicht drei Woche alten Säugling bei einer Gesamtwürdigung der äusseren und inneren Umstände skrupellos im Sinne von <ref-law>. Die Vorinstanz verneine die besondere Skrupellosigkeit genau besehen allein deshalb, weil der Beschwerdegegner "lediglich" mit Eventualvorsatz gehandelt habe. Diese Folgerung sei unzutreffend. Auch bei blossem Eventualvorsatz könnten das Tatmotiv und der Zweck der Tat eine besondere Skrupellosigkeit begründen. Der Beschwerdegegner habe zwar in einer für ihn belastenden Situation gehandelt, doch habe schlicht kein Bezug zwischen dieser Belastungssituation und A.Y._ bestanden. Er habe nicht aufgrund einer Überforderung im Rahmen der Betreuung seines Kindes gehandelt, etwa weil dieses übermässig geschrien hätte. Vielmehr habe er an der völlig unschuldigen A.Y._ seine Aggression und Wut über die Kindsmutter und deren angebliche Fremdbeziehung abreagiert. Ein solches Handeln sei gefühlskalt, egoistisch sowie sinn- und zwecklos und erfülle das Merkmal der Skrupellosigkeit im Sinne des Mordtatbestands (Beschwerde, S. 3-5).
1.2 Eine vorsätzliche Tötung ist als Mord zu qualifizieren, wenn der Täter besonders skrupellos handelt, namentlich wenn sein Beweggrund, der Zweck der Tat oder die Art der Ausführung besonders verwerflich sind (<ref-law>). Mord zeichnet sich nach der Rechtsprechung durch eine aussergewöhnlich krasse Missachtung fremden Lebens bei der Durchsetzung eigener Absichten aus. Es geht um die besonders verwerfliche Auslöschung eines Menschenlebens. Für die Qualifikation verweist das Gesetz in nicht abschliessender Aufzählung auf äussere (Ausführung) und innere Merkmale (Beweggrund, Zweck). Diese müssen nicht alle erfüllt sein, um Mord anzunehmen. Entscheidend ist eine Gesamtwürdigung der äusseren und inneren Umstände der Tat. Eine besondere Skrupellosigkeit kann beispielsweise entfallen, wenn das Tatmotiv einfühlbar und nicht krass egoistisch war, so etwa wenn die Tat durch eine schwere Konfliktsituation ausgelöst wurde. Für Mord typische Fälle sind die Tötung eines Menschen zum Zwecke des Raubes, Tötungen aus religiösem oder politischem Fanatismus oder aus Geringschätzung (<ref-ruling> E. 1a mit Hinweisen).
1.3 Die Vorinstanz erwägt, das Vorgehen des Beschwerdegegners, welcher seine Wut und seinen Frust über die Kindsmutter an A.Y._ ausgelassen habe, sei nicht nachvollziehbar und erscheine egoistisch. Da er seine Tochter aber nicht habe töten wollen, sondern er "bloss" eventualvorsätzlich gehandelt habe, seien im Tatmotiv und dem Zweck der Tat keine besondere Skrupellosigkeit erkennbar und erübrigten sich Ausführungen hierzu. Darauf sei im Rahmen der Strafzumessung zurückzukommen (Entscheid, S. 32). Die Tatausführung mit massiver Gewaltanwendung und Zufügung von grossen Schmerzen (Zusammendrücken des Brustkorbs mit mehrfachen Rippenbrüchen beidseits, längeres Würgen, wiederholtes Schütteln) erscheine zwar als abscheulich, sei jedoch noch nicht als besonders verwerflich zu qualifizieren. Dass es sich beim Opfer um einen knapp drei Wochen alten Säugling gehandelt habe, dürfe für sich betrachtet ebenso wenig zur Annahme von Skrupellosigkeit führen wie der Umstand, dass A.Y._ dem Beschwerdegegner völlig wehr- und hilflos ausgeliefert gewesen sei. Skrupelloses Handeln könne auch nicht darin erblickt werden, dass der Beschwerdegegner A.Y._ nach dem Würgevorgang wieder in ihr Bettchen gelegt und sich an den Computer gesetzt habe, um weiter zu spielen, wie wenn nichts geschehen wäre. Sein Nachtatverhalten indiziere zwar eine Gefühlskälte gegenüber seiner Tochter und eine Geringschätzung menschlichen Lebens, reiche aber zur Begründung von Mord nicht aus. Auch diese Gesichtspunkte seien bei der Strafzumessung zu würdigen (Entscheid, S. 33, 36).
In ihren Strafzumessungserwägungen befasst sich die Vorinstanz ausführlich mit dem Tatmotiv und der Situation des Beschwerdegegners zur Zeit der Tat. Sie stützt sich auf dessen Aussagen und die über ihn erstellten psychiatrischen Gutachten vom 30. Oktober 2009 und 29. September 2010. Sie stellt fest, der Beschwerdegegner sei im Rahmen der Betreuung des Kindes nicht überfordert gewesen. A.Y._ habe auch nicht übermässig geschrien. Der Beschwerdegegner habe vielmehr eine Fremdbeziehung der Kindsmutter vermutet und Zweifel daran gehabt, ob A.Y._ sein leibliches Kind sei. Insofern habe er sich in einer für ihn belastenden Situation befunden. Seine Wut, Aggression und Frustration gegenüber der Kindsmutter und ihrer angeblichen Beziehung zu einem andern Mann habe er an A.Y._ abreagiert, die ihm hierzu nicht den geringsten Anlass gegeben habe. Der Beschwerdegegner habe das Kind wie einen Gegenstand behandelt und nicht als Menschen wahrgenommen, was sich in seiner Aussage manifestiere, A.Y._ sei nicht präsent gewesen, es sei einfach um ihn gegangen. Sein egoistisches Vorgehen sei gänzlich unverständlich, die Tat völlig sinnlos und nicht nachvollziehbar (Entscheid, S. 32, 36, 38 f.).
1.4 Die vorinstanzliche Würdigung der Tat als versuchte vorsätzliche Tötung verletzt in mehrfacher Hinsicht Bundesrecht.
1.4.1 Ob die besondere Skrupellosigkeit vorliegt, ist auf der Basis einer Gesamtwürdigung aller inneren und äusseren Faktoren des konkreten Einzelfalls zu entscheiden. Die für eine Mordqualifikation konstitutiven Elemente sind jene der Tat selber, während Vorleben und Verhalten nach der Tat nur heranzuziehen sind, soweit sie tatbezogen sind und ein Bild der Täterpersönlichkeit ergeben (Urteil 6B_429/2010 vom 24. Januar 2012 E. 4.2). Die massgeblichen Faktoren dürfen nicht isoliert betrachtet werden. Besonders belastende Momente können durch entlastende ausgeglichen werden, wie umgekehrt auch erst das Zusammentreffen mehrerer belastender Umstände, die einzeln womöglich nicht ausgereicht hätten, die Tötung als ein besonders skrupelloses Verbrechen erscheinen lassen kann (GÜNTER STRATENWERTH/GUIDO JENNY/FELIX BOMMER, Schweizerisches Strafrecht, Besonderer Teil I, Bern 2010, § 1 Rz. 22). Die Ausführungen im angefochtenen Entscheid lassen die erforderliche Gesamtwürdigung vermissen. Die Vorinstanz betrachtet die massgeblichen Gesichtspunkte (namentlich den Beweggrund, den Zweck der Tat und die Ausführung) isoliert und folgert, dass keiner der Gesichtspunkte für sich zur Annahme der Qualifikation ausreicht. Der Entscheid ist insoweit rechtsfehlerhaft.
1.4.2 Die Vorinstanz verneint ein besonders verwerfliches Tatmotiv bzw. einen besonders verwerflichen Tatzweck, weil der Beschwerdegegner "bloss" eventualvorsätzlich und nicht mit dem Ziel handelte, seine Tochter zu töten. Damit vermengt sie Fragen der Absicht oder des Handlungsziels beim direkten Vorsatz und des Verwirklichungswillens beim Eventualvorsatz mit Fragen der Skrupellosigkeit. Nach der bundesgerichtlichen Rechtsprechung und der herrschenden Lehre kann Mord auch eventualvorsätzlich begangen werden (<ref-ruling> E. 3b; statt vieler Urteil 6B_215/2012 vom 24. Oktober 2012 E. 2.3.1; CHRISTIAN SCHWARZENEGGER, Basler Kommentar, Strafrecht II, Basel 2007, Rz. 23 zu <ref-law>; STRATENWERTH/JENNY/BOMMER, a.a.O., § 1 Rz. 18; HANS WALDER, Vorsätzliche Tötung, Mord und Totschlag, StRGB Art. 111-113, ZStR 1979, S. 117 ff., S. 158; BERNARD CORBOZ, Les infractions en droit suisse, Volume I, Berne 2010, Rz. 2 zu <ref-law>; MICHEL DUPUIS ET AL, Petit Commentaire du Code pénal, 2012, Rz. 7 zu <ref-law>). Mord unterscheidet sich von der vorsätzlichen Tötung durch die besondere Skrupellosigkeit (<ref-ruling> E. 1a). Diese muss aus der Tat bzw. den Tatumständen hervorgehen und sie als besonders abstossend erscheinen lassen (<ref-ruling> E. 1a; <ref-ruling> E. 2b). Dass der Täter den Tod des Opfers "nur" in Kauf nimmt, schliesst mithin nicht aus, dass die hinter der Tötung bzw. dem Tötungsversuch stehenden Beweggründe und der Zweck der Tat einer besonders krassen Geringschätzung menschlichen Lebens entspringen und besonders verwerflich sein können. Indem die Vorinstanz die konkreten Beweggründe, die den Beschwerdeführer zur Tat veranlassten, nicht im Rahmen der Beurteilung der Skrupellosigkeit würdigte (sondern bei der Strafzumessung), verletzt sie Bundesrecht.
1.4.3 Nach den vorinstanzlichen Feststellungen reagierte der Beschwerdegegner seine frustrationsbedingte Aggression und seine Wut auf die Kindsmutter (wegen deren angeblichen Fremdbeziehung und der Zweifel, ob A.Y._ sein Kind sei) hemmungslos an seiner noch nicht drei Wochen alten Tochter ab und behandelte diese wie einen Gegenstand. Es sei nicht um sie, sondern um ihn gegangen. Darin kommt eine innere Einstellung bzw. Tatmotivation zum Ausdruck, die äusserst egoistisch und bei der Beurteilung der Skrupellosigkeit als besonders verwerflich zu würdigen ist. Denn wer einen andern Menschen zum Objekt seiner Frustration und Wut macht, an deren Entstehung der andere nicht den geringsten Anteil hat, zeigt ein ausserordentliches Mass von Missachtung menschlichen Lebens, indem er dem Opfer jeglichen personalen Eigenwert und das Recht auf körperliche Unversehrtheit vollständig abspricht. Einher mit der besonders verwerflichen Tatmotivation geht weiter der Umstand, dass die versuchte Tötung von A.Y._ nach den vorinstanzlichen Feststellungen als völlig sinnlos und unverständlich erscheint (siehe CORBOZ, a.a.O., Rz. 8 zu <ref-law> mit Hinweis auf <ref-ruling>: "le mobile est aussi particulièrement odieux lorsqu'il apparaît futile; tel est le cas de celui qui tue pour se venger, mais sans motif sérieux"). Auch die Art und Weise, wie der Beschwerdegegner die Tat ausführte, weist auf eine besondere Grausamkeit und Geringschätzung menschlichen Lebens hin. Das Opfer musste erhebliche Gewalttätigkeiten und grosse Schmerzen ertragen. Der Beschwerdegegner drückte ihm den Brustkorb derart ein, dass beidseits Rippen einbrachen. Er würgte es, bis es nicht mehr atmen konnte und blau anlief, und schüttelte es wiederholt so heftig, dass es Hirnverletzungen erlitt. Dass das Kind überlebte, war Zufall. Der Beschwerdegegner zeigte keinerlei Empathie gegenüber seinem Leiden. Er brachte es nach den Übergriffen in sein Bettchen zurück und spielte am Computer, als wäre nichts geschehen. Sein Verhalten während und unmittelbar nach den Tathandlungen enthüllt ein besonderes Mass an Gefühlskälte und steht auch in einem krassen Missverhältnis zur Person des Opfers, einem Säugling, der an der Wut und Frustration bzw. Belastungssituation des Beschwerdegegners keinen Anteil hatte, nichts daran oder dagegen ausrichten konnte und diesem vollkommen schutz- und wehrlos ausgeliefert war. Die Tat erscheint insgesamt als skrupellos im Sinne von <ref-law>. Indem die Vorinstanz diese nicht als Mord einstufte, verletzt sie Bundesrecht.
2. Die Beschwerde ist gutzuheissen und die Sache zur Verurteilung des Beschwerdegegners wegen versuchten Mordes und zur neuen Bemessung der Strafe an die Vorinstanz zurückzuweisen. Auf die Ausführungen des Beschwerdegegners in der Vernehmlassung zur angeblich bundesrechtswidrigen Strafzumessung, insbesondere seinem Vorbringen, er habe die Tat im Sinne von <ref-law> aus eigenem Antrieb nicht zu Ende geführt, ist nicht einzugehen. Er wird sich dazu äussern können, soweit die Vorinstanz im Rahmen ihrer neuen Beurteilung nach Massgabe des Schuldspruchs des Mordes eine höhere Strafe als die bisher ausgefällte in Betracht zieht.
Der obsiegenden Beschwerdeführerin ist keine Entschädigung auszurichten (<ref-law>). Dem Beschwerdegegner wären als unterliegenden Partei grundsätzlich die Gerichtskosten aufzuerlegen (<ref-law>). Er hat indessen ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung gestellt, das gutzuheissen ist, da seine Bedürftigkeit ausgewiesen ist und seine Anträge nicht von vornherein aussichtslos waren (<ref-law>). Damit sind keine Kosten zu erheben und ist der Vertreter des Beschwerdegegners aus der Bundesgerichtskasse zu entschädigen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Obergerichts des Kantons Zürich vom 29. Februar 2012 aufgehoben und die Angelegenheit zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2. Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
3. Es werden keine Kosten erhoben.
4. Dem Rechtsvertreter des Beschwerdegegners, Rechtsanwalt Lars Mathiassen, 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 Obergericht des Kantons Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 8. März 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill