Sachverhalt:
A.
Die Staatsanwaltschaft Winterthur wirft A._ vor, zwischen Dezember 2017 und April 2018 vier Mal ohne gültiges Visum und davon zudem drei Mal auch ohne gültigen Reisepass in die Schweiz eingereist zu sein und sich dort bis zu seiner Verhaftung insgesamt 146 Tage aufgehalten zu haben, obwohl er um die Notwendigkeit eines gültigen Aufenthaltstitels bzw. eines gültigen Reisepasses sowie einer Bewilligung für seine Einreise und den Aufenthalt in der Schweiz gewusst habe.
Das Bezirksgericht verurteilte A._ am 7. August 2018 wegen mehrfacher rechtswidriger Einreise und mehrfachen rechtswidrigen Aufenthalts zu einer (unbedingten) Freiheitsstrafe von sechs Monaten unter Anrechnung von einem Tag Untersuchungshaft und auferlegte ihm die Kosten des Strafverfahrens.
B.
Auf Berufung von A._ verurteilte das Obergericht des Kantons Zürich ihn am 5. Februar 2019 ebenfalls wegen mehrfacher rechtswidriger Einreise und mehrfachen rechtswidrigen Aufenthalts und sprach eine unbedingte Freiheitsstrafe von fünf Monaten aus. Gleichzeitig auferlegte es ihm sämtliche Kosten des Berufungsverfahrens, mit Ausnahme derjenigen der amtlichen Verteidigung, unter Vorbehalt einer Rückzahlungspflicht von A._.
C.
A._ führt Beschwerde in Strafsachen und beantragt zusammengefasst, das Urteil des Obergerichts vom 5. Februar 2019 sei aufzuheben und das Strafverfahren gegen ihn einzustellen. Die Verfahrens- und Gerichtskosten seien auf die Staatskasse zu nehmen und ihm sei für zu Unrecht erlittene Haft eine Genugtuung in Höhe von Fr. 30'000.- zuzusprechen. Eventualiter sei die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. A._ ersucht um unentgeltliche Rechtspflege.
Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich verzichten jeweils auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine Verletzung von Art. 115 Abs. 1 lit. a und b AuG. Es sei zutreffend, dass er im Dezember 2017, ohne über die erforderlichen Papiere zu verfügen, in die Schweiz eingereist sei und anschliessend abgesehen von einer kurzen Aus- und Wiedereinreise im April 2018 bis zum 11. Mai 2018 ununterbrochen ohne gültigen Aufenthaltstitel im Land geblieben sei. Jedoch stehe einer Bestrafung nach Art. 115 Abs. 1 lit. a und b AuG die EU-Rückführungsrichtlinie vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger (RL 2008/115/EU [vormals: EG]; nachfolgend Richtlinie 2008/115) entgegen. Gemäss gefestigter Rechtsprechung des Europäischen Gerichtshofs (EuGH) und des Bundesgerichts sei auf die Verhängung und den Vollzug einer Freiheitsstrafe zu verzichten, wenn gegen den Betroffenen mit illegaler Einreise bzw. illegalem Aufenthalt ein Wegweisungsentscheid ergangen sei und die erforderlichen Entfernungsmassnahmen noch nicht ergriffen worden seien. Zwar hindere die Richtlinie 2008/115 die Vertragsstaaten, zu denen auch die Schweiz zähle, nicht, den illegalen Aufenthalt unter Strafe zu stellen, jedoch dürfe hierdurch die Rückführung nicht verzögert oder vereitelt werden, denn das Rückkehrverfahren gehe der Bestrafung vor, so dass das Opportunitätsprinzip nach Art. 115 Abs. 4 AuG zu einem eigentlichen Strafverfolgungshindernis mutiere, was sowohl bei illegaler Einreise als auch bei illegalem Aufenthalt gelte.
1.2. Die Vorinstanz erwägt, der Beschwerdeführer sei geständig, am 3. Dezember 2017 mit seiner abgelaufenen französischen Aufenthaltsbewilligung und mit seinem jamaikanischen Reisepass, jedoch ohne Aufenthaltsbewilligung in die Schweiz eingereist zu sein und sich hier bis zum 11. Mai 2018 aufgehalten zu haben, wobei er im April 2018 wieder aus- und eingereist sei. Hingegen bestreite er die ihm in der Anklageschrift zur Last gelegten beiden Aus- und Einreisen zwischen dem 17. und 21. Dezember 2017 sowie im Februar 2018. Neben den Aussagen des Beschwerdeführers lägen keine weiteren Beweismittel für die ihm vorgeworfenen Handlungen vor, weshalb gestützt auf seine ersten Einlassungen vor der Polizei, die er anlässlich der erstinstanzlichen Hauptverhandlung und der Berufungsverhandlung bestätigt habe, davon auszugehen sei, dass er am 3. Dezember 2017 ohne die für Einreise und Aufenthalt notwendigen Papiere in die Schweiz eingereist sei und sich hier bis zum 11. Mai 2018 aufgehalten habe und (einmal) für die Dauer von zwei Tagen nach Frankreich zurückgekehrt (und anschliessend wieder eingereist) sei.
Entgegen der Ansicht der Verteidigung stünden die Richtlinie 2008/115 und die Rechtsprechung des Europäischen Gerichtshofes der Verhängung und dem Vollzug einer Freiheitsstrafe nicht entgegen. Zum einen erfasse die Richtlinie 2008/115 nicht die Bestrafung wegen rechtswidriger Einreise, da nur der rechtswidrige Aufenthalt ein Dauerdelikt darstelle, bei dem die von der Richtlinie 2008/115 anvisierte Gefahr bestehe, dass der Staat dem illegal im Land weilenden Ausländer durch Ausübung strafrechtlichen Drucks zum Ausweichen ins umliegende Ausland zu bewegen versuche, statt ihn in den Heimatstaat auszuschaffen. Zum anderen enthalte die Richtlinie 2008/115 keine ausdrückliche Bestimmung, wonach das Rückführungsverfahren einer Bestrafung mit einer Freiheitsstrafe entgegenstehe. Die strafrechtliche Sanktion dürfe lediglich nicht den mit der Richtlinie 2008/115 verfolgten Zweck "Rückführung vor Strafe" vereiteln, so dass selbst eine Freiheitsstrafe mit der Richtlinie 2008/115 vereinbar sei, wenn die Rückführung während des laufenden Strafverfahrens vorangetrieben werde. Zudem ergebe sich aus den Akten des Migrationsamtes des Kantons Zürich, dass zwei Rückführungsversuche im März 2010 und am 4. Dezember 2013 am Widerstand des Beschwerdeführers scheiterten, dieser jedoch am 18. Dezember 2013 erfolgreich nach Jamaika ausgeschafft werden konnte. Bis zu seiner illegalen Einreise in die Schweiz am 29. März 2015 habe er sich laut Akten ununterbrochen im Ausland aufgehalten. Damit entspreche die Situation des Beschwerdeführers der vom EuGH in der Rechtssache Celaj (Urteil vom 1. Oktober 2015 C-290/14) entschiedenen Konstellation, wonach bei Personen, die das Rückkehrverfahren bereits durchlaufen haben und die unter Verstoss gegen ein Einreiseverbot erneut in das Hoheitsgebiet eines Mitgliedstaates eingereist sind, das Rückführungsabkommen einer Freiheitsstrafe nicht im Wege stehe. Demnach sei unerheblich, ob derzeit ein Rückführungsverfahren im Gange sei und welche Bemühungen das Migrationsamt unternehme.
1.3.
1.3.1. Entscheide, die der Beschwerde an das Bundesgericht unterliegen, müssen unter anderem die massgebenden Gründe tatsächlicher und rechtlicher Art, insbesondere die Angabe der angewendeten Gesetzesbestimmungen enthalten (<ref-law>). Aus dem Entscheid muss klar hervorgehen, von welchem festgestellten Sachverhalt die Vorinstanz ausgegangen ist und welche rechtlichen Überlegungen sie angestellt hat. Genügt ein Entscheid diesen Anforderungen nicht, so kann das Bundesgericht ihn in Anwendung von <ref-law> an die kantonale Behörde zur Verbesserung zurückweisen oder aufheben (zum Ganzen: <ref-ruling> E. 2.6.1 S. 237; <ref-ruling> E. 1.2.1; 5A_955/2019 vom 2. Juni 2020 E. 2.1; je mit Hinweisen).
1.3.2. Gemäss Art. 115 Abs. 1 AuG wird u.a. mit Freiheitsstrafe bis zu einem Jahr oder mit Geldstrafe bestraft, wer (lit. a) Einreisevorschriften nach Artikel 5 verletzt und/oder (lit. b) sich rechtswidrig, namentlich nach Ablauf des bewilligungsfreien oder bewilligten Aufenthalts, in der Schweiz aufhält.
1.4. Der angefochtene Entscheid hält im Ergebnis vor Bundesrecht nicht stand. Die von der Vorinstanz getroffenen und für das Bundesgericht grundsätzlich verbindlichen Sachverhaltsfeststellungen (vgl. Art. 97 Abs. 1, Art. 105 Abs. 2 BGG) tragen die rechtlichen Erwägungen nicht.
1.4.1. Vorliegend geht es um eine Verurteilung auf dem Gebiet des Ausländerstrafrechts und deren Vereinbarkeit mit der Richtlinie 2008/115, die aufgrund des Schengen-Abkommens (SR 0.362.31) auch von der Schweiz anzuwenden ist (<ref-ruling> E. 1.4.3; <ref-ruling> E. 1.2 mit Verweis auf den Bundesbeschluss vom 18. Juni 2010 über die Genehmigung und die Umsetzung des Notenaustauschs zwischen der Schweiz und der EG betreffend die Übernahme der Richtlinie 2008/115; AS 5925 2010; Urteil 6B_1365/2019 vom 11. März 2020 E. 2.3.1). Die Richtlinie 2008/115 bezweckt eine minimale Harmonisierung der Verfahren zur Wegweisung und Rückführung von sich illegal aufhaltenden Drittstaatsangehörigen und räumt nach der Rechtsprechung des Bundesgerichts und des EuGH dem verwaltungsrechtlichen Rückführungsverfahren den Vorrang vor strafrechtlichen Sanktionen ein. Sie steht der Bestrafung wegen illegalen Aufenthalts nicht entgegen, jedoch darf die Sanktion die effektive Rückführung nicht gefährden (ausführlich dazu BGE <ref-ruling> E. 1.9, publ. in: Pra 2018 Nr. 78 S. 651; Urteil 6B_1365/2019 vom 11. März 2020 E. 2.3; vgl. auch Urteil [des EuGH] vom 6. Dezember 2012 C- 430/11 Sagor, Rn. 47; Urteil [des EuGH] vom 6. Dezember 2011 C- 329/11 Achughbabian, Rn. 50).
Das Bundesgericht beachtet die Rechtsprechung des EuGH bei der Auslegung der Richtlinie 2008/115. Dies liegt im Interesse einer einheitlichen Rechtsanwendung durch die verschiedenen Mitgliedstaaten und dient der Durchsetzung des Grundsatzes der Parallelität der Rechtsordnungen in den schengenrelevanten Bereichen sowie der Erfüllung der völkerrechtlich übernommenen Verpflichtungen der Schweiz (<ref-ruling> E. 4.2.3). In einem neueren Leitentscheid hat das Bundesgericht festgehalten, dass eine rückführungsrichtlinienkonforme Anwendung von Art. 115 Abs. 1 lit. b AuG verlangt, auf die Verhängung und den Vollzug einer Freiheitsstrafe zu verzichten, wenn gegen den Betroffenen mit illegalem Aufenthalt ein Wegweisungsentscheid erging und die erforderlichen Entfernungsmassnahmen, zu denen auch Zwangsmassnahmen im Sinne von Art. 8 der Richtlinie 2008/115 gehören, noch nicht ergriffen wurden. Demgegenüber ist die Verhängung einer Geldstrafe, soweit sie das Rückführungsverfahren nicht erschwert, mit der Richtlinie 2008/115 vereinbar, da sie unabhängig von den für die Umsetzung der Wegweisung erforderlichen Massnahmen ausgesprochen werden kann (zum Ganzen: BGE <ref-ruling> E. 1.9).
1.4.2. Entgegen der Ansicht der Vorinstanz fällt auch die illegale Einreise in den Anwendungsbereich der Richtlinie 2008/115 und der hierzu ergangenen Rechtsprechung. Aus Art. 3 Ziff. 2 der Richtlinie 2008/115 ergibt sich, dass die Begriffe "illegaler Aufenthalt" und "illegale Einreise" in engem Zusammenhang stehen, da die illegale Einreise in der Regel auch zu einem illegalen Aufenthalt des Drittstaatsangehörigen im Hoheitsgebiet des betreffenden Mitgliedstaats führt. Den Mitgliedstaaten ist es nicht erlaubt, allein wegen des Umstands einer illegalen Einreise, die zu einem illegalen Aufenthalt führt, Strafhaft von Drittstaatsangehörigen zuzulassen, für die das von der Richtlinie 2008/115 geschaffene Rückkehrverfahren noch nicht abgeschlossen wurde (vgl. Urteil [des EuGH] C-47/15 vom 7. Juni 2016, Affum, Rn. 60 ff.). Die in Urteil 1B_162/2015 vom 1. Juli 2015 E. 2.3 ergangene bundesgerichtliche Rechtsprechung (zitiert in 6B_1061/2016 vom 19. Juli 2017 E. 2.2, allerdings ohne Auseinandersetzung mit dem zwischenzeitlich ergangenen Entscheid Affum), wonach die Richtlinie auf die illegale Einreise keine Anwendung findet, ist insoweit überholt. Vom Anwendungsbereich der Richtlinie 2008/115 sind nach der Rechtsprechung lediglich Straftaten ausgenommen, die Drittstaatsangehörige neben einer illegalen Einreise oder dem illegalen Aufenthalt ausserhalb des Ausländerstrafrechts begangen haben, mithin strafbare Handlungen, durch die über die ausländerrechtlichen Regelungen hinausgehende Schutzzwecke tangiert sind (<ref-ruling> E. 2.6.2; Urteile 6B_118/2017 vom 14. Juli 2017 E. 4.4; je mit Hinweisen; EuGH, a.a.O. Rn. 65; vgl. zur aktuellen Gesetzeslage gemäss <ref-law>: Botschaft vom 2. März 2018 zur Revision des Ausländergesetzes [AuG], BBl 2017 1752 f.). Dies ist jedoch bei Art. 115 Abs. 1 lit. a AuG nicht der Fall.
1.4.3. Nicht gefolgt werden kann der Vorinstanz, vorliegend sei im Hinblick auf die Verhängung und Vollstreckung einer Freiheitsstrafe irrelevant, ob gegen den Beschwerdeführer ein Rückführungsverfahren anhängig sei und wie dieses verlaufe. Die tatsächlichen und rechtlichen Umstände im Fall des Beschwerdeführers unterscheiden sich von der durch den EuGH entschiedenen Rechtssache Celaj (C-290/14, Urteil vom 1. Oktober 2015), auf die sich die Vorinstanz beruft, wonach die Richtlinie 2008/115 der Verhängung einer Freiheitsstrafe gegen einen illegal aufhältigen Drittstaatsangehörigen, der nach einer im Rahmen eines früheren Rückkehrverfahrens erfolgten Rückkehr in sein Herkunftsland unter Verstoss gegen ein Einreiseverbot erneut illegal in das Hoheitsgebiet dieses Staates einreist, grundsätzlich nicht entgegensteht.
Dass gegen den Beschwerdeführer im Zeitpunkt des Betretens des schweizerischen Hoheitsgebiets ein Einreiseverbot nach dem AuG bestanden hätte, lässt sich dem angefochtenen Entscheid (wie bereits dem erstinstanzlichen Urteil) nicht entnehmen. Aus den kantonalen Akten ergibt sich zudem, dass das im Rahmen des ersten Rückweisungsverfahrens gegen den Beschwerdeführer am 16. Dezember 2011 gestützt auf Art. 67 AuG verfügte Einreiseverbot nur bis zum 15. Dezember 2016 galt, mithin im Zeitpunkt der vorliegend zu beurteilenden strafbaren Handlungen des Beschwerdeführers nicht mehr bestand. Dabei ist zu berücksichtigen, dass die Durchführung des Rückführungsverfahrens zur Beendigung des ersten illegalen Aufenthalts im Hoheitsgebiet eines Mitgliedstaats sowie die erneute illegale Einreise in das Hoheitsgebiet unter Verstoss gegen ein bestehendes Einreiseverbot kumulativ gegeben sein müssen, wenn wegen (erneuter) illegaler Einreise und illegalen Aufenthaltes eine Freiheitsstrafe ausgesprochen und vollstreckt werden soll. Hat die Anwendung des durch die Richtlinie 2008/115 geschaffenen Verfahrens zur Rückführung eines illegal eingereisten und/oder aufhältigen Drittstaatsangehörigen geführt, gelangt bei erneuten Verstösse gegen das AuG nach Ablauf des im ersten Verfahren ausgesprochenen Einreiseverbots die Richtlinie 2008/115 wieder zur Anwendung.
Im Hinblick auf die der unbedingt ausgesprochenen Freiheitsstrafe von 5 Monaten zugrunde liegenden Verstösse des Beschwerdeführers gegen das AuG zwischen Dezember 2017 und April 2018 kann nicht von einem gescheiterten Rückführungsverfahren gesprochen werden. Der Beschwerdeführer konnte im Dezember 2013 erfolgreich in sein Heimatland Jamaika verbracht werden und hat mit seinen hier zu beurteilenden erneuten illegalen Einreisen und den anschliessenden illegalen Aufenthalten nicht gegen das bis zum 15. Dezember 2016 verhängte Einreiseverbot verstossen. Die ausländerechtliche Situation unterscheidet sich in diesem Fall nicht von derjenigen eines erstmals rechtswidrig einreisenden und/oder aufhältigen Drittstaatsangehörigen, weshalb auch im vorliegenden Verfahren die Richtlinie 2008/115 zur Anwendung gelangt und die wegen Verstosses gegen Art. 115 Abs. lit. a und b AuG ausgesprochene Strafe nicht zu einer Beeinträchtigung des Rückführungsverfahrens führen darf. Dass der Beschwerdeführer bereits zu einem früheren Zeitpunkt am 29. März 2015 während des bestehenden Einreiseverbots illegal in die Schweiz einreisen wollte und hierbei verhaftet wurde, ist im Hinblick auf die zu beurteilenden und sanktionierenden Straftaten zwischen Dezember 2017 und April 2018 irrelevant, da sie nicht Gegenstand des vorliegenden Verfahrens sind und der Beschwerdeführer zudem für seinen illegalen Einreiseversuch mit Strafbefehl vom 30. März 2015 zu einer unbedingten Geldstrafe von 60 Tagessätzen zu Fr. 30. - verurteilt und unmittelbar nach Frankreich ausgewiesen wurde.
1.4.4. Zusammenfassend ist festzuhalten, dass sich dem angefochtenen Entscheid und den Akten nicht entnehmen lässt, ob die Voraussetzungen für die ausgesprochene und sofort vollzogene fünfmonatige Freiheitsstrafe gegeben waren. Der angefochtene Entscheid verletzt mithin <ref-law>. Die Vorinstanz wird weitere Abklärungen und Feststellungen treffen müssen, ob gegen den Beschwerdeführer im Zeitpunkt der Vollstreckung der fünfmonatigen Freiheitsstrafe ein Rückführungsverfahren eingeleitet worden war und welche Bemühungen das Migrationsamt ergriffen hatte. Die Vorinstanz wird im Hinblick auf die Rechtmässigkeit der verhängten und vollstreckten Freiheitsstrafe beachten müssen, dass die Richtlinie 2008/115 auch dann Anwendung findet und das geschaffene Rückkehrverfahren abzuschliessen ist, wenn die illegale Einreise über eine Binnengrenze erfolgte und zu einem illegalen Aufenthalt führt und der betreffende Drittstaatsangehörige in Anwendung eines Abkommens oder einer Vereinbarung im Sinne von Art. 6 Abs. 3 der Richtlinie 2008/115 von einem anderen Mitgliedstaat wieder aufgenommen werden kann.
Da die Freiheitsstrafe trotz fehlender Rechtskraft bereits vollstreckt wurde, kann offenbleiben, ob in Präzisierung der bundesgerichtlichen Rechtsprechung die Verhängung und der Vollzug einer Freiheitsstrafe mit der Richtlinie 2008/115 in Einklang zu bringen sind, wenn sichergestellt ist, dass der Vollzug dieser Freiheitsstrafe beendet wird, sobald die physische Verbringung des Betroffenen aus dem Mitgliedstaat möglich ist. Ob die Vorgehensweise der Staatsanwaltschaft, zeitgleich mit dem Strafbefehl den (vorzeitigen) Vollzug der unbedingten fünfmonatigen Freiheitsstrafe gegen den zum damaligen Zeitpunkt noch nicht anwaltlich vertretenen Beschwerdeführer zu "genehmigen", zulässig war, erscheint - insbesondere vor dem Hintergrund der vorstehend aufgezeigten Rechtsprechung des Bundesgerichts und des Europäischen Gerichtshofs - zweifelhaft, kann jedoch im vorliegenden Verfahren aufgrund der unvollständigen Sachverhaltsfeststellungen nicht abschliessend beurteilt werden.
2.
2.1. Trotz Rückweisung der Sache zu neuer Entscheidung an die Vorinstanz ist aus prozessökonomisch Gründen auf die Rüge des Beschwerdeführers einzutreten, die Vorinstanz habe ihm unter Verletzung von Art. 428 Abs. 1 Satz 1 und Art. 436 Abs. 1 i.V.m. <ref-law> trotz Freispruchs von den Vorwürfen, um den 21. Dezember 2017 und im Februar 2018 zwei weitere Male rechtswidrig in die Schweiz eingereist zu sein, sowie einer Strafreduktion vom einem Monat sämtliche Kosten des Berufungsverfahrens auferlegt und die Rückforderung der Kosten der amtlichen Verteidigung vorbehalten.
2.2. Die Vorinstanz führt in Bezug auf den Kosten und Entschädigungsentscheid aus, der Beschwerdeführer sei anklagegemäss der mehrfachen rechtswidrigen Einreise im Sinne von Art. 115 Abs. 1 lit. a i.V.m. Art. 5 Abs. 1 lit. a AuG und des mehrfachen rechtswidrigen Aufenthaltes gemäss Art. 115 lit. b AuG schuldig zu sprechen und mit einer unbedingten Freiheitsstrafe von 5 Monaten zu bestrafen. Da der Beschwerdeführer mit seinen Anträgen vollumfänglich unterliege, seien ihm die gesamten Kosten, mit Ausnahme derjenigen für die amtliche Verteidigung unter Vorbehalt einer Rückforderung, gemäss <ref-law> aufzuerlegen. Bei diesem Verfahrensausgang bestehe kein Anspruch auf eine Genugtuung und der erstinstanzliche Kostenentscheid sei zu bestätigen.
2.3. Gemäss <ref-law> tragen die Parteien die Kosten des Rechtsmittelverfahrens nach Massgabe ihres Obsiegens oder Unterliegens. Ob bzw. inwieweit eine Partei im Sinne dieser Bestimmung obsiegt oder unterliegt, hängt davon ab, in welchem Ausmass ihre vor der zweiten Instanz gestellten Anträge gutgeheissen werden (Urteile 6B_572/2018 vom 1. Oktober 2018 E. 5.1.2; 6B_565/2015 vom 10. Februar 2016 E. 4.1, nicht publ. in: <ref-ruling>, aber in: Pra 2016 Nr. 83 S. 77; 6B_1025/2014 vom 9. Januar 2015 E. 2.4.1; je mit Hinweisen).
2.4. Die Rüge erweist sich als begründet. Die Staatsanwaltschaft wirft dem Beschwerdeführer in der Anklageschrift vor, viermal illegal in die Schweiz eingereist zu sein. Die Vorinstanz erachtet im Gegensatz zum Bezirksgericht jedoch nur zwei Einreisen unter Verstoss gegen das AuG für erwiesen, weshalb wegen der nicht erwiesenen Vorwürfe der rechtswidrigen Einreisen um den 21. Dezember 2017 und im Februar 2018 ein (Teil-) Freispruch hätte ergehen müssen. Da die Urteilsformel neben den Schuldsprüchen den Beschwerdeführer nicht "im Übrigen" freispricht, erledigt sie den durch die Anklage vorgegebenen Prozessgegenstand nicht vollständig (vgl. <ref-ruling> E. 1.3). Neben den zwei (Teil-) Freisprüchen hat die Vorinstanz zudem die Strafe um einen Monat reduziert. Bei diesem Verfahrensausgang kann nicht von einem vollständigen Unterliegen des Beschwerdeführers gesprochen werden. Dass die Vorinstanz das Dispositiv des Bezirksgerichts unverändert übernimmt und den Beschwerdeführer erneut wegen mehrfacher rechtswidriger Einreise und mehrfachen rechtswidrigen Aufenthalts (jeweils in zwei statt vier Fällen) verurteilt hat, ändert nichts daran, dass dieser im Berufungsverfahren teilweise obsiegt i.S.v. <ref-law>.
3.
Da die Erwägungen des vorinstanzlichen Entscheids eine vollständige Rechtsüberprüfung durch das Bundesgericht nicht zulassen, kann der Antrag auf Zusprechung einer Entschädigung wegen unrechtmässiger Haft hingegen nicht behandelt werden.
4.
Die Beschwerde erweist sich als begründet. Bei diesem Verfahrensausgang sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG), womit das Gesuch um unentgeltliche Rechtspflege gegenstandslos wird. Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Die Entschädigung wird praxisgemäss seinem Rechtsvertreter ausgerichtet.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, das Urteil des Obergerichts des Kantons Zürich vom 5. Februar 2019 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Es werden keine Kosten erhoben.
3.
Der Kanton Zürich hat den Vertreter des Beschwerdeführers, Rechtsanwalt Jean Louis Scenini, für das bundesgerichtliche Verfahren mit Fr. 3'000.- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 17. Dezember 2020
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Held