Sachverhalt:
A.
Am 20. Dezember 2010 kam es zwischen den Eheleuten X._ und Y._ in deren Wohnung zu einer Auseinandersetzung, in deren Verlauf X._ seiner Frau mehrmals mit der Faust ins Gesicht schlug, sie zu Boden stiess und würgte. Y._ erlitt infolge der Kompression der Halsgefässe flohstichartige Lidhaut-, Bindehaut- und Trommelfelleinblutungen. Aufgrund einer temporären Sauerstoffunterversorgung und Beeinträchtigung der Blutzufuhr zum Gehirn bestand für sie konkrete Lebensgefahr. X._ wusste, dass es tödlich enden kann, "wenn man jemand[em] den Hals/die Luft zumacht".
B.
Das Obergericht des Kantons Zürich sprach X._ am 3. Mai 2013 im Berufungsverfahren vom Vorwurf der Gefährdung des Lebens frei. Es verurteilte ihn aufgrund der unangefochtenen Schuldsprüche wegen einfacher Körperverletzung und mehrfacher Übertretung des Betäubungsmittelgesetzes unter Berücksichtigung einer zu vollziehenden Reststrafe von 222 Tagen zu einer unbedingten Freiheitsstrafe von 27 Monaten und einer Busse von Fr. 600.--.
C.
Die Oberstaatsanwaltschaft des Kantons Zürich führt Beschwerde in Strafsachen mit dem Antrag, das obergerichtliche Urteil sei aufzuheben und die Sache zu neuer Entscheidung an das Obergericht zurückzuweisen.
Das Obergericht verzichtet auf eine Vernehmlassung. X._ beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten ist. Er ersucht um unentgeltliche Prozessführung und Verbeiständung.

Erwägungen:
1.
1.1. Die Beschwerdeführerin rügt eine Verletzung von Art. 129 StGB und des Anspruchs auf rechtliches Gehör. Die Vorinstanz verneine das Tatbestandsmerkmal der Skrupellosigkeit zu Unrecht. Von Notwehr oder einer Provokation, die das Würgen und die damit verbundene Lebensgefahr als verständlich oder zumindest nachvollziehbar erscheinen liesse, könne keine Rede sein. Der Beschwerdegegner habe mit seinem gewalttätigen Vorgehen keine auch nur teilweisen positiven Zwecke verfolgt. Grösse und Nähe der Lebensgefahr, die massiver nicht hätten sein können, belegten die Skrupellosigkeit seines Vorgehens. Zudem komme die Vorinstanz ihrer Begründungspflicht nicht nach. Das subjektive Tatbestandsmerkmal der Skrupellosigkeit sei ein komplexes und schwierig bestimmbares Tatbestandsmerkmal, das nicht mit der oberflächlichen Begründung einer (allfälligen) Provokation des Beschwerdegegners durch das Opfer ausgeschlossen werden könne.
1.2. Die Vorinstanz erwägt zusammengefasst, der Anklagesachverhalt sei - bis auf die dem Beschwerdegegner nicht nachweisbaren Fusstritte gegen seine Ehefrau - erstellt. Aufgrund der Gutachten des Instituts für Rechtsmedizin der Universität Zürich bestünden keine Zweifel, dass der Beschwerdegegner seine Ehefrau im Laufe der Auseinandersetzung auch gewürgt und infolge der verursachten Stauungsblutungen Lebensgefahr für diese bestanden habe. Der Beschwerdegegner sei sich der mit dem Würgen herbeigeführten unmittelbaren Lebensgefahr bewusst gewesen und habe " (direkt) vorsätzlich" gehandelt. Aufgrund der Begleitumstände der Tat, namentlich des nachweisbar heftigen und längeren Streits, sei jedoch nicht auszuschliessen, dass der Beschwerdegegner durch die Geschädigte vorgängig provoziert worden sei. Es fehle mithin am Nachweis der Skrupellosigkeit.
1.3.
1.3.1. Die aus dem Anspruch auf rechtliches Gehör (Art. 29 Abs. 2 BV) fliessende Begründungspflicht (Art. 81 Abs. 3 lit. a StPO) verpflichtet das Gericht, seinen Entscheid zu begründen. Das Gericht kann sich auf die für den Entscheid wesentlichen Punkte beschränken, muss jedoch wenigstens kurz die Überlegungen nennen, von denen es sich hat leiten lassen und auf die sich sein Entscheid stützt. Die Begründung muss so abgefasst sein, dass der Betroffene in voller Kenntnis der Tragweite des Entscheids die Sache weiterziehen kann und der Rechtsmittelinstanz die Überprüfung der Rechtsanwendung möglich ist (vgl. <ref-ruling> E. 2.2 S. 84 mit Hinweisen).
1.3.2. Gemäss Art. 129 StGB wird mit Freiheitsstrafe bis zu fünf Jahren oder Geldstrafe bestraft, wer einen Menschen in skrupelloser Weise in unmittelbare Lebensgefahr bringt. Objektiv ist eine konkrete, unmittelbare Lebensgefahr erforderlich. Dies ist der Fall, wenn sich aus dem Verhalten des Täters direkt die Wahrscheinlichkeit oder nahe Möglichkeit der Todesfolge ergibt. Bezüglich der unmittelbaren Lebensgefahr ist direkter Vorsatz erforderlich, Eventualvorsatz genügt nicht. Skrupellos ist ein in schwerem Grade vorwerfbares, rücksichts- oder hemmungsloses Verhalten (vgl. <ref-ruling> E. 5.1 S. 8; Urteil 6B_583/2013 vom 20. Dezember 2013 E. 3.3.3). Das Tatbestandsmerkmal der Skrupellosigkeit dient dazu, den Anwendungsbereich von Art. 129 StGB auf besonders schwere Fälle zu beschränken, da grundsätzlich jede vorsätzliche unmittelbare Lebensgefährdung eines Menschen sittlich zu missbilligen ist, wenn kein Rechtfertigungsgrund vorliegt. Der dem Täter zu machende qualifizierte Grad an Verwerflichkeit muss sich in einem Verhalten manifestieren, dass jegliche Rücksicht auf das Leben anderer Menschen vermissen lässt. Gedacht ist an Situationen, in denen das Leben von Mitmenschen massiv gefährdet wird, dem Täter jedoch kein Tötungsvorsatz nachgewiesen werden kann (vgl. Botschaft vom 26. Juni 1985 über die Änderung des Schweizerischen Strafgesetzbuches und des Militärstrafgesetzes [Strafbare Handlungen gegen Leib und Leben, gegen die Sittlichkeit und gegen die Familie], BBl 1985 II 1037).
1.4. Unstreitig ist, dass der Beschwerdegegner den objektiven Tatbestand von Art. 129 StGB erfüllt und hinsichtlich der mit dem Würgen herbeigeführten unmittelbaren Lebensgefahr für seine Ehefrau " (direkt) vorsätzlich" gehandelt hat. Weder beschreibt der Anklagesachverhalt, den die Vorinstanz (mit Ausnahme der nicht nachgewiesenen Fusstritte) ihren Erwägungen zugrunde legt, eine irgendwie geartete Provokation seitens der Geschädigten, noch trifft die Vorinstanz hierzu (Sachverhalts-) Feststellungen. Aufgrund des blossen Hinweises einer allfälligen, nicht näher beschriebenen Provokation kann nicht überprüft werden, ob die Vorinstanz das Tatbestandsmerkmal der Skrupellosigkeit zu Recht verneint hat. Ihre Erwägungen genügen den Begründungsanforderungen nicht.
1.5. Die Beschwerde ist gutzuheissen. Der Beschwerdegegner unterliegt mit seinem Antrag auf Abweisung der Beschwerde, weshalb er grundsätzlich kostenpflichtig wird (Art. 66 Abs. 1 BGG). Jedoch ist sein Gesuch um unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren gutzuheissen. Er bedurfte zur Wahrnehmung seines Anspruchs auf rechtliches Gehörs eines Rechtsbeistands und seine Bedürftigkeit scheint erstellt. Sein Antrag auf Abweisung der Beschwerde kann nicht als aussichtslos bezeichnet werden (Art. 64 Abs. 1 und Abs. 2 BGG). Der Beschwerdegegner wird jedoch auf Art. 64 Abs. 4 BGG aufmerksam gemacht. Danach hat die Partei der Gerichtskasse Ersatz zu leisten, wenn sie später dazu in der Lage ist. Rechtsanwalt Dario Zarro ist aus der Bundesgerichtskasse angemessen zu entschädigen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, das Urteil des Obergerichts des Kantons Zürich, II. Strafkammer, vom 3. Mai 2013 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen. Für das bundesgerichtliche Verfahren wird ihm Rechtsanwalt Dario Zarro als unentgeltlicher Anwalt beigegeben.
3.
Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdegegner auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4.
Dem Vertreter des Beschwerdegegners wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 2'000.-- ausgerichtet.
5.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 10. Februar 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Held