Sachverhalt:
A.
Das Bundesverwaltungsgericht wies am 31. Oktober 2011 die vom georgischen Staatsangehörigen X._ gegen seinen ablehnenden Asylbescheid erhobene Beschwerde ab. X._ hätte aufgrund des Entscheids des Bundesamts für Migration (BFM) die Schweiz nach mehrfacher Verlängerung der Ausreisefrist per 25. Juli 2012 verlassen müssen. Dies tat er nicht und wurde am 24. Januar 2013 anlässlich einer Personenkontrolle in Zürich angehalten und verhaftet.
B.
Das Obergericht des Kantons Zürich verurteilte X._ am 21. November 2013 im Berufungsverfahren wegen unerlaubten Aufenthaltes im Sinne des Ausländergesetzes (AuG; SR 142.20) zu einer bedingten Geldstrafe von 40 Tagessätzen zu Fr. 10.-- unter Anrechnung von zwei Tagen Untersuchungshaft.
C.
X._ führt Beschwerde in Strafsachen und beantragt, das Urteil des Obergerichts sei aufzuheben, und er sei vom Vorwurf der Widerhandlung gegen das Ausländergesetz freizusprechen. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung.
Das Obergericht und die Staatsanwaltschaft haben auf Vernehmlassungen verzichtet.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, seine Verurteilung verstosse gegen die Richtlinie 2008/115/EG des Europäischen Parlaments und des Rates vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger (ABl. L 348 vom 24. Dezember 2008, S. 98 ff.; nachfolgend: EU-Rückführungsrichtlinie).
1.2. Die Vorinstanz erwägt, die EU-Rückführungsrichtlinie stehe einem Schuldspruch wegen unerlaubten Aufenthaltes im Sinne von Art. 115 AuG nicht entgegen. Die bedingt ausgesprochene Geldstrafe beeinträchtige nicht die mit der EU-Rückführungsrichtlinie angestrebte gemeinsame Rückführungspolitik der Mitgliedsstaaten. Die grundsätzliche Befugnis der Mitgliedsstaaten, illegalen Aufenthalt in ihrem Staatsgebiet zu sanktionieren, werde vom EuGH nicht in Frage gestellt. Weder handle es sich um eine unverhältnismässige Strafe, mit der die Ausreise des Beschwerdeführers erzwungen werden solle, noch beeinträchtige sie dessen freiwillige oder zwangsweise Rückkehr in seinen Heimatstaat. Dem Argument der Subsidiarität des Strafrechts gegenüber ausländerrechtlichen (Zwangs-) Massnahmen sei entgegenzuhalten, dass solche nur deshalb unterblieben sind, weil der Beschwerdeführer gegenüber dem Migrationsamt des Kantons Zürich den Eindruck erweckt habe, Vorbereitungen zur Ausreise zu treffen. Unter diesen Voraussetzungen erscheine es nicht stossend, dass er für seinen unberechtigten Aufenthalt in der Schweiz nach Ablauf der Ausreisefrist belangt werde.
2.
Das Bundesgericht hat sich ausführlich und grundlegend mit der Anwendung der EU-Rückführungsrichtlinie und dem Verhältnis zur innerstaatlichen Strafbarkeit wegen rechtswidrigen Aufenthaltes befasst. Auf diese grundlegenden Ausführungen kann verwiesen werden (vgl. Urteil 6B_196/2012 vom 24. Januar 2013 E. 2). Zwar räumt die EU-Rückführungsrichtlinie dem verwaltungsrechtlichen Rückführungsverfahren den Vorrang vor strafrechtlichen Sanktionen ein, jedoch sind nationale Strafbestimmungen nicht ausgeschlossen, wenn im verwaltungsrechtlichen Verfahren alles für den Vollzug der Rückkehrentscheidung Zumutbare vorgekehrt worden ist, dieser indessen am Verhalten des Betroffenen scheitert (vgl. Urteile 6B_188/2012 vom 17. April 2012 E. 5; 6B_617/2012 und 6B_618/2012 vom 11. März 2013 E. 1.5) und die Ausreise objektiv möglich ist (Urteil 6B_482/2010 vom 7. Oktober 2010 E. 3.2.2 und 3.2.3).
3.
Unstreitig ist, dass die Ausreise des Beschwerdeführers objektiv möglich war (und immer noch ist). Soweit er geltend macht, das verwaltungsrechtliche Rückführungsverfahren gehe strafrechtlichen Sanktionen vor, kann er hieraus nichts zu seinen Gunsten ableiten. Aus den Verfahrensakten ergibt sich, dass der Beschwerdeführer explizit darauf hingewiesen wurde, dass das Migrationsamt mit dem Vollzug der Wegweisung beauftragt war. Er wusste, dass er bei Nichtbefolgung der behördlichen Anweisungen mit Zwangsmassnahmen rechnen musste. Nach den verbindlichen Feststellungen der Vorinstanz hat das kantonale Migrationsamt nur deswegen keine Zwangsmassnahmen ergriffen, weil der Beschwerdeführer in der Folgezeit den Anschein erweckte, er treffe die für seine Ausreise erforderlichen Vorbereitungen. Mit diesen Ausführungen setzt sich der Beschwerdeführer nicht auseinander. Dass das Migrationsamt unter diesen Umständen nicht darauf vertrauen konnte, er werde freiwillig ausreisen und in Beachtung des Verhältnismässigkeitsprinzips bundesrechtskonform auf die Ergreifung von Zwangsmassnahmen zur Umsetzung der Wegweisung verzichten durfte, legt der Beschwerdeführer nicht dar. Die bedingte Geldstrafe von 40 Tagessätzen zu Fr. 10.-- ist auch nicht geeignet, die Rückführung des Beschwerdegegners zu verzögern oder zu verhindern. Der angefochtene Entscheid verletzt kein Bundesrecht.
4.
Die Beschwerde ist abzuweisen. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist gutzuheissen, da die Bedürftigkeit des Beschwerdeführers ausgewiesen ist und sein Rechtsbegehren nicht offensichtlich aussichtslos war (<ref-law>). Es sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Rechtsvertreter des Beschwerdeführers ist angemessen zu entschädigen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen. Ihm wird für das bundesgerichtliche Verfahren Fürsprecher Sararard Arquint als unentgeltlicher Anwalt beigegeben.
3.
Es werden keine Gerichtskosten erhoben.
4.
Dem Anwalt des Beschwerdeführers 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, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 5. August 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Held