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.