Sachverhalt: A. Die Strafverfolgungsbehörden der Kantone Zürich und Aargau führten (teilweise) zur gleichen Zeit je eine Strafuntersuchung gegen A._ (und andere Personen). Das von der Oberstaatsanwaltschaft des Kantons Zürich gestellte Gesuch, die Strafbehörden des Kantons Aargau zu verpflichten, sämtliche A._ (und weiteren Personen) zur Last gelegten Straftaten gemeinsam zu verfolgen, wies die Beschwerdekammer des Bundesstrafgerichts mit Beschluss vom 20. März 2012 ab und ordnete die (getrennte) Verfolgung und Beurteilung durch die Kantone für die bei ihnen hängigen Strafverfahren an. B. Das Obergericht des Kantons Zürich verurteilte A._ am 9. März 2017 für im Zeitraum von Mai 2008 bis Juli 2009 begangener Handlungen wegen falscher Anschuldigung, gewerbsmässigen Betrugs, mehrfacher, teilweise versuchter Veruntreuung, Urkundenfälschung, Geldwäscherei, Sachbeschädigung und Anstiftung zum mehrfachen Erschleichen eines Ausweises zu einer Freiheitsstrafe von 4 1⁄2 Jahren unter Anrechnung der ausgestandenen Haft und des vorzeitigen Strafvollzugs. Der Mitbeschuldigte B._ erhob gegen das Urteil Beschwerde in Strafsachen beim Bundesgericht. Am 13. Dezember 2017 verurteilte das Obergericht des Kantons Aargau A._ für Handlungen zwischen Juni und September 2011 wegen einfacher Körperverletzung und mehrfacher, teilweise versuchter Nötigung zu einer teilbedingten Freiheitsstrafe von 3 Jahren, unter Aufschub eines Strafteils von 24 Monaten, bei einer Probezeit von 2 Jahren. Dieses Urteil erwuchs in Rechtskraft. C. A._ stellte mit Eingabe vom 27. März 2018 beim Obergericht des Kantons Zürich ein Gesuch um (nachträgliche) Gesamtstrafenbildung gemäss Art. 34 Abs. 3 StPO. Das Obergericht sistierte das Verfahren mit Beschluss vom 14. Mai 2018 bis zum Abschluss des bundesgerichtlichen Beschwerdeverfahrens des Mittäters B._. Nach teilweiser Gutheissung der Beschwerde von B._ und Rückweisung der Sache zu neuer Entscheidung stellte das Obergericht des Kantons Zürich mit Urteil (und Beschluss) vom 2. Oktober 2018 fest, dass das (erste) Berufungsurteil vom 9. März 2017 in Bezug auf A._ in Rechtskraft erwachsen ist und beurteilte die Sache betreffend B._ erneut. Dieses Urteil erwuchs unangefochten in Rechtskraft. Am 9. Mai 2019 wies das Obergericht des Kantons Zürich das Gesuch von A._ um nachträgliche Gesamtstrafenbildung ab und auferlegte ihm die Verfahrenskosten. D. A._ führt Beschwerde in Strafsachen und beantragt, das Urteil des Obergerichts des Kantons Zürich vom 9. Mai 2019 sei aufzuheben und es sei eine Zusatzstrafe von 3 Jahren Freiheitsstrafe zum Urteil des Obergerichts des Kantons Aargau vom 13. Dezember 2017 auszufällen. Die im zürcherischen Verfahren erstandene Haft und der vorzeitige Strafvollzug seien an die Zusatzstrafe anzurechnen. Eventualiter seien die obergerichtlichen Urteile vom 9. März 2017 und vom 13. Dezember 2017 aufzuheben und es sei eine Gesamtfreiheitsstrafe von 6 Jahren auszufällen, auf die der bisherige Freiheitsentzug aus beiden Verfahren anzurechnen sei. Subeventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. A._ ersucht um unentgeltliche Rechtspflege. Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich verzichten auf Stellungnahmen.