Sachverhalt:
A.
X._, dessen Asylgesuch abgewiesen und dessen Wegweisung verfügt worden war, arbeitete von Mai 2014 bis November 2014 mit einem Unterbruch von zwei Monaten selbstständig in einem Coiffeursalon in Zürich und verdiente dabei monatlich zwischen Fr. 1'000.-- und Fr. 1'500.--. In der Zeit vom 1. Dezember 2014 bis 7. Januar 2015 arbeitete er gegen ein Entgelt von netto Fr. 3'000.-- in einem anderen Coiffeursalon in Zürich. Er arbeitete jeweils ohne über die für komorische Staatsangehörige nötige Arbeitsbewilligung zu verfügen, was er wusste.
B.
Die Staatsanwaltschaft Zürich-Limmat verurteilte X._ mit Strafbefehl vom 19. November 2014 wegen Widerhandlung gegen Art. 115 Abs. 1 lit. b des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG; SR 142.20) (rechtswidriger Aufenthalt) und Art. 115 Abs. 1 lit. c i.V.m. Art. 11 Abs. 1 AuG (Ausübung einer nichtbewilligten Erwerbstätigkeit) zu einer unbedingten Freiheitsstrafe von 120 Tagen. X._ erhob gegen den Strafbefehl Einsprache. Die Staatsanwaltschaft stellte daraufhin das Verfahren wegen rechtswidrigen Aufenthalts mit Verfügung vom 20. Februar 2015 mangels Strafbarkeit (objektive Unmöglichkeit der legalen Ausreise) ein. Hinsichtlich des Vorwurfs der Erwerbstätigkeit ohne Bewilligung erhob sie beim Bezirksgericht Zürich Anklage.
C.
Das Bezirksgericht Zürich erklärte X._ am 19. Januar 2016 der mehrfachen Erwerbstätigkeit ohne Bewilligung im Sinne von Art. 115 Abs. 1 lit. c AuG schuldig. Es ordnete dessen Rückversetzung in den Vollzug der mit Strafbefehl der Staatsanwaltschaft Zürich-Limmat am 2. März 2012 ausgefällten Freiheitsstrafe an (Strafrest 32 Tage) und verurteilte ihn unter Einbezug des Strafrests aus dem Strafbefehl vom 2. März 2012 zu einer unbedingten Gesamtfreiheitsstrafe von 130 Tagen.
Das Obergericht des Kantons Zürich bestätigte auf Berufung von X._ am 25. Oktober 2016 das erstinstanzliche Urteil.
D.
X._ beantragt mit Beschwerde in Strafsachen zur Hauptsache, er sei von Schuld und Strafe freizusprechen. Eventualiter sei ihm der bedingte Vollzug zu gewähren. Subeventualiter sei er zu gemeinnütziger Arbeit anstatt zu einer Freiheitsstrafe zu verurteilen.
E.
Das Obergericht und die Staatsanwaltschaft verzichteten auf eine Stellungnahme.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine Verletzung von Art. 14 und 18 StGB. Es liege ein entschuldbarer Notstand vor, weshalb er vom Vorwurf der Widerhandlung gegen Art. 115 Abs. 1 lit. c AuG freizusprechen sei. Er habe nicht als Sozialschmarotzer gelten wollen, was ein massiver Angriff auf die Ehre als strafrechtlich geschütztes Rechtsgut sei. Er könne die Schweiz mangels Ausweispapieren nicht verlassen und sei gemäss Art. 4 AuG zu integrieren. Die Bestrafung widerspreche daher auch der ratio legis des Arbeitsverbots, die darin bestehe, illegale Migranten von der Einreise in die Schweiz abzuschrecken.
1.2. Art. 4 AuG statuiert das allgemeine Ziel der Integration von längerfristig und rechtmässig anwesenden Ausländern (vgl. MARC SPESCHA, in: Migrationsrecht, Spescha et al. [Hrsg.], 4. Aufl. 2015, N. 1 zu Art. 4 AuG). Die Bestimmung verankert jedoch keinen individuellen Rechtsanspruch auf bewilligungsfreien Zugang zum Arbeitsmarkt, welcher der im AuG und in Art. 43 des Asylgesetzes vom 26. Juni 1998 (AsylG; SR 142.31) vorgesehenen Pflicht zur Einholung einer Arbeitsbewilligung sowie der Strafbestimmung von Art. 115 Abs. 1 lit. c AuG vorgehen könnte. Soweit der Beschwerdeführer unter Hinweis auf Art. 4 AuG sinngemäss geltend macht, sein Verhalten falle nicht unter den Straftatbestand von Art. 115 Abs. 1 lit. c AuG, kann ihm nicht gefolgt werden.
Das Arbeitsverbot von <ref-law> ist mit der EMRK grundsätzlich vereinbar (ausführlich dazu <ref-ruling> E. 2 und 3). Nach der Rechtsprechung kann sich bei langer Anwesenheit und jahrelanger Nothilfeabhängigkeit eines weggewiesenen Asylbewerbers in ausserordentlichen Situationen aus Art. 8 EMRK (Anspruch auf Schutz des Privatlebens) jedoch ein Anspruch auf Bereinigung des Anwesenheitsstatus (vorläufige Aufnahme gemäss Art. 83 Abs. 1 AuG oder asylrechtlicher Härtefall) bzw. auf Erteilung einer Arbeitsbewilligung gemäss Art. 85 Abs. 6 AuG ergeben (siehe dazu <ref-ruling> E. 3.3). Selbst daraus kann allerdings nicht abgeleitet werden, der Beschwerdeführer habe sich eigenmächtig über das Arbeitsverbot hinwegsetzen und ohne entsprechende Bewilligung einer Arbeitstätigkeit nachgehen dürfen.
1.3.
1.3.1. <ref-law> verlangt für die Annahme eines entschuldbaren Notstands eine unmittelbare, nicht anders abwendbare Gefahr für Leib, Leben, Freiheit, Ehre, Vermögen oder andere hochwertige Güter. Die Vorinstanz verneint einen entschuldbaren Notstand. Sie erwägt, dass es den Beschwerdeführer bedrückt habe, dass er nicht habe arbeiten können, sei nachvollziehbar. Diese Beeinträchtigung der Gefühlslage habe aber nicht die Intensität einer konkreten unmittelbaren, nicht anders abwehrbaren Gefahr für dessen psychische Gesundheit erreicht. Objektive Anhaltspunkte, dass die psychische Gesundheit des Beschwerdeführers ernsthaft gefährdet gewesen sei, lägen nicht vor (angefochtenes Urteil E. 4.3 S. 16).
Die Sachverhaltsfeststellung der Vorinstanz kann vor Bundesgericht nur gerügt werden, wenn sie offensichtlich unrichtig bzw. willkürlich im Sinne von <ref-law> ist (<ref-law>; <ref-ruling> E. 5.4 S. 324 mit Hinweisen). Die Rüge der Willkür muss in der Beschwerde explizit vorgebracht und substanziiert begründet werden (<ref-law>; <ref-ruling> E. 5.4 S. 324 mit Hinweisen). Dass die Vorinstanz willkürlich eine Gefahr für seine psychische Gesundheit verneint haben könnte, behauptet der Beschwerdeführer nicht, weshalb darauf nicht weiter einzugehen ist.
1.3.2. Die Ehrverletzungstatbestände des StGB (vgl. Art. 173 ff.) schützen den Ruf, ein ehrbarer Mensch zu sein, d.h. sich so zu benehmen, wie nach allgemeiner Anschauung ein charakterlich anständiger Mensch sich zu verhalten pflegt (<ref-ruling> E. 2.1.1 S. 315; <ref-ruling> E. 2.1 S. 115; Urteile 6B_918/2016 vom 28. März 2017 E. 6.3; 6B_683/2016 vom 14. März 2017 E. 1.3). Inwiefern die strafrechtlich geschützte Ehre des Beschwerdeführers tangiert sein könnte, weil er über keine Arbeitsbewilligung verfügte und in der Schweiz daher nicht arbeiten durfte, ist nicht ersichtlich und zeigt dieser auch nicht rechtsgenügend auf.
1.4. Die Rügen des Beschwerdeführers sind unbegründet, soweit sie den gesetzlichen Begründungsanforderungen überhaupt zu genügen vermögen.
2.
2.1. In seiner Eventualbegründung rügt der Beschwerdeführer eine Verletzung von <ref-law>. Er habe aus achtenswerten Beweggründen gehandelt, weil er nicht als Sozialschmarotzer habe gelten wollen. Dies müsse sich mindestens mildernd auf das Verschulden und die Strafe auswirken.
2.2. Das Bundesgericht hat die Grundsätze der Strafzumessung nach <ref-law> wiederholt dargelegt (<ref-ruling> E. 5.4 ff.; <ref-ruling> E. 2.1; je mit Hinweisen). Darauf kann verwiesen werden. Es liegt im Ermessen des Sachgerichts, in welchem Umfang es die verschiedenen Strafzumessungsfaktoren berücksichtigt. Das Bundesgericht greift auf Beschwerde hin nur in die Strafzumessung ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen bzw. in Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet hat (<ref-ruling> E. 5.6 mit Hinweis).
2.3. Die Vorinstanz erachtet für die beurteilte Widerhandlung gegen Art. 115 Abs. 1 lit. c AuG in Würdigung der massgeblichen Strafzumessungsgründe eine Strafe in der Höhe von 110 Tagen Freiheitsstrafe bzw. 110 Tagessätzen Geldstrafe für angemessen (angefochtenes Urteil E. 1.7 S. 21). Sie erwägt u.a., der Deliktszeitraum von insgesamt ca. sechs Monaten sei zwar als relativ kurz zu bewerten. Zu berücksichtigen sei jedoch, dass der Beschwerdeführer hinsichtlich beider Deliktsphasen in anderem Zusammenhang und daher zufällig bei der illegalen Erwerbstätigkeit ertappt worden sei und dass es sich um mehrfache Delinquenz sehr kurz hintereinander handle (angefochtenes Urteil E. 1.2.1 S. 17). Das Motiv des Beschwerdeführers, er habe einfach seinen Lebensunterhalt verdienen wollen, leuchte ein, sei aber zu relativieren, da dieser auf legalem Wege um finanzielle Unterstützung hätte nachsuchen können. Dies gelte umso mehr in Anbetracht der einschlägigen Vorstrafen und - bezüglich der zweiten zu beurteilenden Deliktsphase ab 1. Dezember 2014 - angesichts der ersten Verhaftung vom 18. November 2014 und des darauf ergangenen Strafbefehls vom 19. November 2014 wegen Erwerbstätigkeit ohne Bewilligung (angefochtenes Urteil E. 1.2.2 S. 18). Der Beschwerdeführer habe wenige Tage nach dem Strafbefehl vom 19. Dezember 2014 die dort geahndete Delinquenz ab 1. Dezember 2014 offenbar unbeeindruckt wieder aufgenommen. Dies lasse an Einsicht fehlen, weshalb er sich nicht auf ein geringes Verschulden im Sinne von <ref-law> berufen könne (angefochtenes Urteil E. 1.6 S. 20).
2.4. Der Beschwerdeführer reiste im Dezember 2006 mit einer gefälschten französischen Identitätskarte in die Schweiz ein. In der Folge wurden ihm gestützt auf die von ihm getätigten falschen Angaben zu Unrecht zwei Arbeitsbewilligungen sowie am 1. Oktober 2007 eine Aufenthaltsbewilligung B erteilt. Er wurde deswegen mit rechtskräftigem Strafbefehl vom 4. März 2009 wegen Urkundenfälschung (<ref-law>), mehrfacher Täuschung der Behörden nach Art. 118 Abs. 1 AuG und mehrfachen Vergehens gegen das Ausländergesetz im Sinne von Art. 115 Abs. 1 lit. c AuG verurteilt (kant. Akten, Urk. E-5/10). Er ist daher einschlägig vorbestraft. Er wurde zudem nach dem Strafbefehl vom 19. November 2014 während des noch laufenden Verfahrens erneut in gleicher Weise straffällig. Die Vorinstanz berücksichtigt dies zu Recht bei der Strafzumessung. Achtenswerte Beweggründe im Sinne von <ref-law> liegen nicht vor. Die Vorinstanz trägt den konkreten Tatumständen sowie dem Motiv des Beschwerdeführers im Rahmen von <ref-law> zutreffend bei der Bewertung von dessen Verschulden Rechnung. Sie setzt sich in ihren Erwägungen zur Strafzumessung mit den wesentlichen schuldrelevanten Komponenten auseinander. Dass sie sich dabei von rechtlich nicht massgebenden Gesichtspunkten hätte leiten lassen oder wesentliche Gesichtspunkte nicht berücksichtigt hätte, ist nicht ersichtlich. Die vorinstanzliche Strafzumessung ist nicht zu beanstanden und die Rüge des Beschwerdeführers unbegründet.
3.
3.1. Der Beschwerdeführer argumentiert zudem, die Vorinstanz habe ihm zu Unrecht den bedingten Vollzug verweigert. Da er sich inzwischen mit seinem Status als "Sozialschmarotzer wider Willen" abgefunden habe und von den sozialen Diensten des Kantons Neuenburg unterstützt werde, könne entgegen der Vorinstanz nicht von einer negativen Legalprognose ausgegangen werden.
3.2.
3.2.1. Das Gericht schiebt den Vollzug einer Geldstrafe, von gemeinnütziger Arbeit oder einer Freiheitsstrafe von mindestens sechs Monaten und höchstens zwei Jahren in der Regel auf, wenn eine unbedingte Strafe nicht notwendig erscheint, um den Täter von der Begehung weiterer Verbrechen oder Vergehen abzuhalten (<ref-law>). Die kurze Freiheitsstrafe ist in <ref-law> geregelt. Das Gericht kann auf eine Freiheitsstrafe von weniger als sechs Monaten nur erkennen, wenn die Voraussetzungen von <ref-law> für eine bedingte Strafe nicht gegeben sind (<ref-law>).
3.2.2. Im Rahmen von <ref-law> genügt für den bedingten Vollzug das Fehlen einer ungünstigen Prognose. Die Gewährung des bedingten Strafaufschubs setzt mit anderen Worten nicht die positive Erwartung voraus, der Täter werde sich bewähren, sondern es genügt die Abwesenheit der Befürchtung, dass er es nicht tun werde. Der Strafaufschub ist deshalb die Regel, von der grundsätzlich nur bei ungünstiger Prognose abgewichen werden darf. Er hat im breiten Mittelfeld der Ungewissheit den Vorrang (<ref-ruling> E. 2.1; <ref-ruling> E. 7.3; <ref-ruling> E. 4.2.2; je mit Hinweisen).
Bei der Prüfung, ob der Verurteilte für ein dauerndes Wohlverhalten Gewähr bietet, hat das Gericht eine Gesamtwürdigung aller wesentlichen Umstände vorzunehmen. In die Beurteilung miteinzubeziehen sind neben den Tatumständen auch das Vorleben und der Leumund sowie alle weiteren Tatsachen, die gültige Schlüsse auf den Charakter des Täters und die Aussichten seiner Bewährung zulassen. Ein relevantes Prognosekriterium ist insbesondere die strafrechtliche Vorbelastung (BGE <ref-ruling> E. 4.2.1). Einschlägige Vorstrafen sind bei der Prognosestellung zwar als erheblich ungünstiges Element zu gewichten, sie schliessen den bedingten Vollzug allerdings nicht notwendigerweise aus (Urteile 6B_358/2014 vom 26. Juni 2014 E. 2.3; 6B_435/2013 vom 19. Juli 2013 E. 1.2; 6B_140/2012 vom 14. September 2012 E. 3; je mit Hinweisen).
Dem Sachrichter steht bei der Prüfung des künftigen Legalverhaltens ein Ermessensspielraum zu. Das Bundesgericht greift nur ein, wenn dieser sein Ermessen über- bzw. unterschreitet oder missbraucht und damit Bundesrecht verletzt (BGE <ref-ruling>40 E. 4.2 S. 143 mit Hinweis).
3.2.3. Der Beschwerdeführer ist mit dem Strafbefehl vom 4. März 2009 teils einschlägig vorbestraft (vgl. oben E. 2.4). Mit Strafbefehlen der Staatsanwaltschaft Zürich-Limmat vom 2. und 16. März 2012 erfolgten weitere Schuldsprüche wegen rechtswidrigen Aufenthalts betreffend die Zeit vom 24. August 2011 bis am 29. Februar 2012 bzw. vom 9. Oktober 2009 bis am 16. Juni 2011 sowie wegen Übertretung gegen das Betäubungsmittelgesetz nach <ref-law>, begangen in der Zeit vom 1. Januar 2010 bis am 16. Juni 2011. Der Beschwerdeführer wurde am 7. August 2014 bedingt aus dem Vollzug der im Strafbefehl vom 2. März 2012 ausgesprochenen Freiheitsstrafe von 90 Tagen entlassen (angefochtenes Urteil E. 2.1 S. 21; Urteil des Bezirksgerichts E. 3.2 S. 21; kant. Akten, Urk. 69).
3.2.4. Die Verurteilung wegen rechtswidrigen Verweilens im Land erlaubt nach der Rechtsprechung nicht die Stellung einer schlechten Prognose, wenn dem Beurteilten in der Zwischenzeit eine Aufenthaltsbewilligung erteilt wurde und er sich mithin rechtmässig in der Schweiz aufhält (BGE <ref-ruling> E. 7). Der Beschwerdeführer verfügt gemäss dem angefochtenen Entscheid zwar über keine Aufenthaltsbewilligung für den Verbleib in der Schweiz. Aus der Einstellungsverfügung vom 20. Februar 2015 geht jedoch hervor, dass er am 26. und 27. März 2013 bei der Komorischen Botschaft in Paris vorsprach, um Papiere für seine Ausreise erhältlich zu machen, was ihm verweigert worden sei. Die Staatsanwaltschaft hält in der Einstellungsverfügung vom 20. Februar 2015 fest, es sei davon auszugehen, dass der Beschwerdeführer mangels Ausweispapieren nicht habe ausreisen können. Es lasse sich nicht widerlegen, dass er seiner Mitwirkungspflicht um Beschaffung von Papieren seinen Möglichkeiten entsprechend nachgekommen sei, diese Bemühungen aber bisher nicht zum Erfolg geführt hätten. Die Staatsanwaltschaft stellte das Strafverfahren gegen den Beschwerdeführer wegen rechtswidrigen Aufenthalts in der Zeit nach seiner Haftentlassung am 7. August 2014 daher ein (kant. Akten, Urk. 15). Dass dieser zuvor wiederholt wegen rechtswidrigen Aufenthalts in der Schweiz verurteilt wurde, führt daher noch nicht zu einer schlechten Prognose, da aufgrund der Einstellungsverfügung vom 20. Februar 2015 und mangels abweichender Feststellungen der Vorinstanz (siehe dazu auch hinten E. 4.3.2) davon auszugehen ist, dass sich dieser mangels Reisepapieren gegenwärtig durch seinen Verbleib in der Schweiz nicht mehr im Sinne von Art. 115 Abs. 1 lit. b AuG strafbar macht (vgl. dazu hinten E. 5.4.1 und die dort zitierten Entscheide).
Bei der Prognosebildung unberücksichtigt zu bleiben hat auch die Vorstrafe wegen Widerhandlung gegen das Betäubungsmittelgesetz im Sinne von <ref-law>. Bei <ref-law> handelt es sich um eine blosse Übertretung. Der unbedingte Strafvollzug soll den Täter gemäss <ref-law> von der Begehung weiterer Verbrechen oder Vergehen abhalten. Zukünftige Übertretungen spielen für die Prognose bei der Frage, ob eine Strafe für ein Verbrechen oder Vergehen zu vollziehen ist, daher keine Rolle, auch wenn der fehlende Wille, sich gesetzeskonform zu verhalten, ein massgebendes Kriterium ist (SCHNEIDER/GARRÉ, in: Basler Kommentar, Strafrecht I, 3. Aufl. 2013, N. 43 zu <ref-law>; siehe auch Urteil 6B_18/2008 vom 15. Mai 2008 E. 2.4.3).
3.2.5. Für die Prognosebildung herangezogen werden darf jedoch, dass der Beschwerdeführer nach der bedingten Entlassung aus dem Strafvollzug am 7. August 2014 mit den vorliegend beurteilten Widerhandlungen gegen Art. 115 Abs. 1 lit. c AuG (Erwerbstätigkeit ohne Bewilligung) wieder deliktisch in Erscheinung trat. Er liess sich zudem selbst von der laufenden Strafuntersuchung nicht beeindrucken, da er kurze Zeit nach dem Strafbefehl vom 19. November 2014 erneut einer nicht bewilligten Erwerbstätigkeit als Coiffeur nachging (vgl. oben E. 2.4). Nicht zu beanstanden ist unter diesen Umständen, wenn die Vorinstanz von einer ungünstigen Prognose ausgeht und auf eine unbedingte Strafe erkennt. Was der Beschwerdeführer dagegen einwendet, überzeugt nicht. Dass er heute Sozialhilfe bezieht, schliesst nicht von vornherein aus, dass er in Zukunft versucht sein könnte, mittels illegaler Arbeit ein besseres Einkommen zu erzielen. Die Vorinstanz hat das ihr zustehende Ermessen nicht überschritten, wenn sie die Voraussetzungen von <ref-law> für eine bedingte Strafe als nicht erfüllt erachtet.
4.
4.1. Der Beschwerdeführer macht eine Verletzung von Art. 37 und Art. 40 Abs. 1 StGB geltend. Die Vorinstanz hätte ihn anstelle der kurzen Freiheitsstrafe zu gemeinnütziger Arbeit verurteilen müssen. Er befinde sich nicht illegal in der Schweiz. Er könne diese mangels Ausweispapieren nicht verlassen, weshalb das letzte Strafverfahren gegen ihn wegen rechtswidrigen Aufenthalts mit Verfügung vom 20. Februar 2015 eingestellt worden sei. Aus den Akten sei nichts ersichtlich, wonach sich an dieser Situation in den nächsten Jahren etwas ändern würde, zumal auch die Behörden des Kantons Neuenburg zufolge Aussichtslosigkeit nichts unternehmen würden, um ihm Reisepapiere zu beschaffen und die Ausreise zu erzwingen. Folglich bestehe entgegen der Vorinstanz sehr wohl die Aussicht, dass er noch längere Zeit in der Schweiz bleiben dürfe und müsse. Es sei daher nicht ersichtlich, warum keine gemeinnützige Arbeit angeordnet worden sei. Mangels Möglichkeit für ihn und die Neuenburger Behörden, Reisepapiere zu beschaffen, sei sein Verbleib in der Schweiz entgegen der Vorinstanz nicht etwa ausgeschlossen, sondern im Gegenteil noch für Jahre zwingend zu erwarten. Er besitze gemäss den vorinstanzlichen Feststellungen in der Schweiz auch ein soziales Netz. Die Vorinstanz lasse unberücksichtigt, dass bei unbedingten Strafen von weniger als sechs Monaten von Gesetzes wegen zwingend auf Geldstrafe oder gemeinnützige Arbeit zu erkennen sei.
4.2.
4.2.1. Für Strafen von weniger als sechs Monaten ist nach geltendem Recht grundsätzlich eine Geldstrafe oder gemeinnützige Arbeit auszusprechen (Art. 34 Abs. 1, Art. 37 Abs. 1, Art. 40 und 41 Abs. 1 StGB). Das Gericht kann mit Zustimmung des Täters an Stelle einer Freiheitsstrafe von weniger als sechs Monaten oder einer Geldstrafe bis zu 180 Tagessätzen gemeinnützige Arbeit von höchstens 720 Stunden anordnen (<ref-law>). Auf eine Freiheitsstrafe von weniger als sechs Monaten kann gemäss <ref-law> nur erkannt werden, wenn zu erwarten ist, dass eine Geldstrafe oder gemeinnützige Arbeit nicht vollzogen werden kann. Das Gericht hat diese Strafform näher zu begründen (<ref-law>). <ref-law> verankert für Strafen unter sechs Monaten eine gesetzliche Prioritätsordnung zugunsten nicht freiheitsentziehender Sanktionen. Das Gericht hat daher immer zu prüfen, ob eine Geldstrafe oder gemeinnützige Arbeit angeordnet werden kann. Dahinter steckte das zentrale Anliegen des auf den 1. Januar 2007 in Kraft getretenen reformierten Sanktionenrechts, die sozial desintegrierenden kurzen Freiheitsstrafen zurückzudrängen (<ref-ruling> E. 2.4; <ref-ruling> E. 4.1; <ref-ruling> E. 3.1). Die Möglichkeit, ausnahmsweise eine unbedingte Freiheitsstrafe von weniger als sechs Monaten zu verhängen, ist nach der bundesrätlichen Botschaft in den Fällen gerechtfertigt, in denen gewährleistet werden muss, dass der Staat seinen Strafanspruch durchsetzen kann. Dies ist namentlich der Fall, wenn die Voraussetzungen für das Aussetzen der Strafe nicht gegeben sind, der Verurteilte aber gemeinnützige Arbeit zum Vornherein verweigert und - wie etwa bei Fluchtgefahr - auch eine Geldstrafe voraussichtlich nicht bezahlen wird (vgl. Botschaft vom 21. September 1998 zur Änderung des Schweizerischen Strafgesetzbuches [Allgemeine Bestimmungen, Einführung und Anwendung des Gesetzes] und des Militärstrafgesetzes sowie zu einem Bundesgesetz über das Jugendstrafrecht, BBl 1999 1979 ff., 2044).
4.2.2. Die Anordnung von gemeinnütziger Arbeit rechtfertigt sich nach der Rechtsprechung nur, solange wenigstens Aussicht besteht, dass der Betroffene auch nach einem allfälligen Strafvollzug für sein Fortkommen in der Schweiz bleiben darf. Sinn der Arbeitsstrafe ist die Wiedergutmachung zugunsten der lokalen Gemeinschaft sowie die Erhaltung des sozialen Netzes des Verurteilten. Dort, wo ein Verbleib des Ausländers von vornherein ausgeschlossen ist, lässt sich dies nicht erreichen. Besteht demnach bereits im Urteilszeitpunkt kein Anwesenheitsrecht oder steht fest, dass über seinen ausländerrechtlichen Status endgültig entschieden worden ist und er die Schweiz verlassen muss, hat die gemeinnützige Arbeit nach der Rechtsprechung als unzweckmässige Sanktion auszuscheiden (BGE <ref-ruling> E. 6.3.3.4 S. 110). Befindet sich die verurteilte Person im Ausland und ist sie nicht berechtigt, in die Schweiz einzureisen, sind die Voraussetzungen für die gemeinnützige Arbeit daher nicht erfüllt (Urteil 6B_546/2008 vom 27. November 2008 E. 3.3). Im Urteil 6B_819/2008 vom 26. Dezember 2008 E. 2.3 entschied das Bundesgericht zudem, ein Asylbewerber, dessen Asylgesuch rechtskräftig abgewiesen und dessen Wegweisung verfügt worden sei, erfülle die Voraussetzungen für die gemeinnützige Arbeit nicht. Im Urteil 6B_709/2013 vom 27. Januar 2014 E. 2 bestätigte es besagte Rechtsprechung in Bezug auf eine Person, die sich illegal in der Schweiz aufhielt und gegenüber welcher ein gültiges Einreiseverbot verfügt wurde. Anders als vorliegend erfolgten in den erwähnten Entscheiden allerdings Schuldsprüche wegen illegalen Aufenthalts in der Schweiz nach Art. 115 Abs. 1 lit. b AuG bzw. Art. 23 Abs. 1 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121, in Kraft bis am 31. Dezember 2007). Anhaltspunkte, dass die betroffenen Personen die Schweiz objektiv gar nicht verlassen konnten, lagen damit nicht vor.
4.3.
4.3.1. Die Vorinstanz erwägt unter Hinweis auf das erstinstanzliche Urteil, das Bundesverwaltungsgericht habe am 24. August 2011 endgültig über das zweite Asylgesuch des Beschwerdeführers entschieden, wobei dessen Wegweisung verfügt worden sei. Ebenfalls sei das Gesuch des Beschwerdeführers um Anerkennung als Staatenloser mit Verfügung vom 27. Mai 2015 abgelehnt und das Verfahren rechtskräftig abgeschlossen worden. Der rechtmässige Verbleib des Beschwerdeführers in der Schweiz sei damit ausgeschlossen, weshalb die gemeinnützige Arbeit als unzweckmässige Sanktion ausscheide (angefochtenes Urteil E. 2.4 S. 23; erstinstanzliches Urteil E. 5.2 S. 23).
4.3.2. Die vorinstanzlichen Erwägungen lassen unberücksichtigt, dass dem Beschwerdeführer eine Ausreise aus der Schweiz gemäss der Einstellungsverfügung vom 20. Februar 2015 mangels Reisepapieren objektiv gar nicht möglich ist. Aus der Einstellungsverfügung vom 20. Februar 2015 geht hervor, dass dieser am 26. und 27. März 2013 zweimal bei der Komorischen Botschaft in Paris vorsprach, wobei ihm Ausweispapiere wegen seiner Homosexualität verweigert worden seien. Die Staatsanwaltschaft stellte das Strafverfahren gegen den Beschwerdeführer wegen rechtswidrigen Aufenthalts nach Art. 115 Abs. 1 lit. b AuG daher ein (kant. Akten, Urk. 15; oben E. 3.2.4).
Die Argumentation der Vorinstanz greift folglich zu kurz und steht im Widerspruch zur Einstellungsverfügung vom 20. Februar 2015. Der rechtskräftige Wegweisungsentscheid aus dem Jahre 2011 bedeutet unter den konkreten Umständen noch nicht, dass der Beschwerdeführer die Schweiz auch verlassen kann. Die Vorinstanz begründet nicht, weshalb sie entgegen der Einstellungsverfügung vom 20. Februar 2015 zur Auffassung gelangt, der Beschwerdeführer müsse und könne in absehbarer Zeit in sein Heimatland zurückkehren. Sie zeigt insbesondere nicht auf, welche allfälligen behördlichen Anstrengungen seit dem erfolglosen Versuch des Beschwerdeführers im März 2013, sich bei der Komorischen Botschaft Ausweispapiere zu verschaffen, unternommen wurden. Dessen Verurteilung zu einer kurzen unbedingten Freiheitsstrafe verstösst daher gegen <ref-law>. Nach dieser Bestimmung darf eine vollziehbare Freiheitsstrafe von weniger als sechs Monaten nur verhängt werden, wenn zu erwarten ist, dass weder eine Geldstrafe noch eine gemeinnützige Arbeit vollzogen werden kann. Davon kann nicht ausgegangen werden, wenn eine Wegweisung zwar verfügt wurde, diese aber aus vollzugstechnischen Gründen (insb. zufolge Weigerung der ausländischen Behörden, Reisedokumente auszustellen) nicht möglich erscheint und sich die betroffene Person voraussichtlich daher noch auf unbestimmte Zeit in der Schweiz aufhalten wird. Ist der Vollzug einer Wegweisung nicht möglich, hat das Bundesamt für Migration unter gewissen Voraussetzungen gar die vorläufige Aufnahme zu verfügen (vgl. Art. 83 ff. AuG; <ref-law>; Art. 16 ff. der Verordnung vom 11. August 1999 über den Vollzug der Weg- und Ausweisung sowie der Landesverweisung von ausländischen Personen [VVWAL; SR 142.281]; <ref-ruling> E. 2.3). Vorläufig aufgenommene Personen erhalten den Ausländerausweis F, der für höchstens zwölf Monate ausgestellt und unter Vorbehalt von Art. 84 AuG verlängert wird (Art. 85 Abs. 1 AuG; Art. 20 Abs. 2 VVWAL). Aus einer vorläufigen Aufnahme kann zwar kein Anspruch auf ein gefestigtes Aufenthaltsrecht abgeleitet werden (RUEDI ILLES, in: Bundesgesetz über die Ausländerinnen und Ausländer [AuG], Caroni/Gächter/Thurnherr [Hrsg.], 2010, N. 3 zu Art. 85 AuG). Dennoch hat sich gezeigt, dass die grosse Mehrheit der vorläufig aufgenommenen Personen während einer längeren Zeit oder sogar für immer in der Schweiz bleibt (PETER BOLZLI, in: Migrationsrecht, Spescha et al. [Hrsg.], 4. Aufl. 2015, N. 1 Vorbemerkungen zu Art. 85-88 AuG; siehe auch Vorläufige Aufnahme und Schutzbedürftigkeit: Analyse und Handlungsoptionen, Bericht des Bundesrats vom 14. Oktober 2016 in Erfüllung der Postulate 11.3954, 13.3844 und 14.3008, S. 4 und 9). Da es sich bei der Freiheitsstrafe im Vergleich zur Geldstrafe und zur gemeinnützigen Arbeit um die eingriffsintensivere Sanktion handelt (vgl. BGE <ref-ruling> E. 4.2.2 mit Hinweisen), darf die Unmöglichkeit des Vollzugs von gemeinnütziger Arbeit im Sinne von <ref-law> nicht leichthin bejaht werden, wenn sich die beschuldigte Person seit längerer Zeit in der Schweiz aufhält, keine Fluchtgefahr vorliegt sowie begründete Aussicht besteht, dass sie bspw. mangels Ausreisemöglichkeit auch künftig noch hier verweilen wird.
Die Angelegenheit ist in diesem Sinne zur ergänzenden Sachverhaltsabklärung an die Vorinstanz zurückzuweisen. Diese wird sich im Rahmen der Neubeurteilung auch mit dem aktuellen Stand des Wegweisungsverfahrens zu befassen haben. Dabei wird sie insbesondere zu prüfen haben, ob die Ausreise des Beschwerdeführers überhaupt möglich ist bzw. ob seitens der Behörden Schritte unternommen wurden, um diesem die Ausreise zu ermöglichen. Dessen Rüge ist begründet.
4.4. Da es um eine Verurteilung auf dem Gebiet des Ausländerstrafrechts geht, stellt sich zudem die Frage der Anwendbarkeit der EU-Rückführungsrichtlinie (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.), welche nach der Rechtsprechung des Europäischen Gerichtshofs (EuGH) und des Bundesgerichts dem verwaltungsrechtlichen Rückführungsverfahren den Vorrang vor strafrechtlichen Sanktionen einräumt (ausführlich dazu Urteile 6B_274/2016 vom 15. Mai 2017 E. 1, zur Publikation vorgesehen; 6B_106/2016 vom 7. Dezember 2016 E. 1; 6B_196/2012 vom 24. Januar 2013 E. 2; je mit Hinweisen). Die erwähnte Rechtsprechung betrifft die Bestrafung von Ausländern wegen rechtswidrigen Aufenthalts im Sinne von Art. 115 Abs. 1 lit. b AuG. Sie ist nach einem neueren Grundsatzurteil des Bundesgerichts auch bei einem Schuldspruch nach Art. 119 Abs. 1 AuG wegen Missachtung einer der Umsetzung der Wegweisung dienenden Ein- oder Ausgrenzung im Sinne von Art. 74 Abs. 1 lit. b und c AuG anwendbar, nicht jedoch bei einer Ein- oder Ausgrenzung gestützt auf Art. 74 Abs. 1 lit. a AuG zum Schutz der öffentlichen Sicherheit und Ordnung (Urteil 6B_366/2016 vom 15. Mai 2017 E. 2.6, zur Publikation vorgesehen). Vom Anwendungsbereich der EU-Rückführungsrichtlinie ebenfalls nicht erfasst wird die Bestrafung eines weggewiesenen Ausländers wegen illegaler Erwerbstätigkeit in der Schweiz (Urteil 6B_196/2012 vom 24. Januar 2013 E. 2.2.1). Daran ist weiterhin festzuhalten. Zwar dient auch das Arbeitsverbot nach <ref-law> der Umsetzung der Konsequenzen des negativen Asylentscheids (Wegweisung), da damit verhindert werden soll, dass zusätzliche Anreize für einen rechtswidrigen Verbleib in der Schweiz geschaffen werden (vgl. <ref-ruling> E. 3.2.2; Urteil 2C_17/2017 vom 22. Mai 2017 E. 2.1). Darüber hinaus stehen bei der Frage, ob Ausländer in der Schweiz einer unselbstständigen oder selbstständigen Erwerbstätigkeit nachgehen dürfen, jedoch auch wirtschaftliche Interessen auf dem Spiel (vgl. dazu die in Art. 18 ff. AuG statuierten Voraussetzungen für die Zulassung zu einem Aufenthalt mit Erwerbstätigkeit). Wer als Ausländer in der Schweiz einer nicht bewilligten Erwerbstätigkeit nachgeht, kann sich folglich nicht auf die EU-Rückführungsrichtlinie berufen, um einer Verurteilung zu einer Freiheitsstrafe oder zu gemeinnütziger Arbeit zu entgehen.
5.
5.1. Der Beschwerdeführer kritisiert schliesslich, die Vorinstanz hätte ihn für die Vorstrafe wegen illegalen Aufenthalts nicht in den Vollzug zurückversetzen dürfen. Der illegale Aufenthalt sei ein Delikt, dessen er sich mangels Ausreisemöglichkeit seit Jahren gar nicht mehr schuldig machen könne. Eine Rückversetzung in einen solchen Strafvollzug sei daher unangemessen und ungerechtfertigt. Er sei homosexuell. Gemäss offiziellem Personenstand sei er männlichen Geschlechts, besitze aber eine weibliche Geschlechtsidentität und befinde sich derzeit im Prozess einer medizinischen Geschlechtsumwandlung. In Bezug auf einen Gefängnisaufenthalt sei auch die laufende Geschlechtsumwandlung zu berücksichtigen. Die Zuweisung an eine Strafanstalt für Männer oder Frauen würde erhebliche Probleme bereiten.
5.2.
5.2.1. Dem bedingt aus dem Freiheitsentzug Entlassenen wird eine Probezeit auferlegt (<ref-law>). Begeht er während der Probezeit ein Verbrechen oder Vergehen, so ordnet das für die Beurteilung der neuen Tat zuständige Gericht die Rückversetzung an (<ref-law>). Ist trotz des während der Probezeit begangenen Verbrechens oder Vergehens nicht zu erwarten, dass der Verurteilte weitere Straftaten begehen wird, so verzichtet das Gericht auf eine Rückversetzung (<ref-law>). Es kann den Verurteilten verwarnen und die Probezeit um höchstens die Hälfte der von der zuständigen Behörde ursprünglich festgesetzten Dauer verlängern (<ref-law>).
5.2.2. Ein während der Probezeit begangenes Verbrechen oder Vergehen führt nicht zwingend zum Widerruf der bedingten Entlassung. Im Rahmen von <ref-law> muss - wie beim Entscheid über die bedingte Entlassung (vgl. <ref-law>) - genügen, dass vernünftigerweise erwartet werden kann, der Verurteilte werde keine weiteren Straftaten begehen. Angesichts der bloss relativen Sicherheit von Legalprognosen dürfen an diese Erwartung keine übermässig hohen Anforderungen gestellt werden (Urteile 6B_715/2015 vom 21. März 2016 E. 2.1; 6B_1085/2013 vom 22. Oktober 2014 E. 4.2.1; 6B_303/2007 vom 6. Dezember 2007 E. 6; siehe auch Urteile 6B_69/2012 vom 14. September 2012 E. 2.4.2; 6B_765/2008 vom 7. April 2009 E. 2.3.2, nicht publ. in: <ref-ruling>, die unter Hinweis auf den zu <ref-law> ergangenen BGE <ref-ruling>40 E. 4.3 eine eigentliche Schlechtprognose verlangen).
5.2.3. Die Prüfung der Bewährungsaussichten des Täters ist anhand einer Gesamtwürdigung aller wesentlichen Umstände vorzunehmen (ausführlich Urteile 6B_1085/2013 vom 22. Oktober 2014 E. 4.2.1; 6B_1034/2013 vom 31. März 2014 E. 2.1; 6B_235/2010 vom 17. Mai 2010 E. 2.2). Bei der Beurteilung der Bewährungsaussichten im Rahmen von Art. 89 Abs. 1 und 2 StGB ist zudem - wie beim Widerruf des bedingten Strafvollzugs bzw. beim Verzicht darauf nach Art. 46 Abs. 1 und 2 StGB (vgl. BGE <ref-ruling>40 E. 4.5) - zu berücksichtigen, ob die neue Strafe bedingt oder unbedingt ausgesprochen wird. Das Gericht kann zum Schluss kommen, vom Widerruf der bedingten Entlassung und der Rückversetzung in den Strafvollzug sei abzusehen, weil die neue Strafe vollzogen wird (Urteile 6B_69/2012 vom 14. September 2012 E. 2.4.2; 6B_765/2008 vom 7. April 2009 E. 2.3.2, nicht publ. in: <ref-ruling>; anders Urteil 6B_1034/2013 vom 31. März 2014 E. 2.8).
Der Widerruf einer bedingten Entlassung nach <ref-law> hat weitreichende Konsequenzen, da er zu einer Rückversetzung in den Strafvollzug führt und der Betroffene daher mit einem erneuten Freiheitsentzug konfrontiert ist. Die Rückversetzung muss daher auch mit dem Verhältnismässigkeitsprinzip vereinbar sein (vgl. <ref-ruling> E. 3.4.4).
5.3.
5.3.1. Nach Art. 115 Abs. 1 lit. b AuG macht sich strafbar, wer sich rechtswidrig, namentlich nach Ablauf des bewilligungsfreien oder des bewilligten Aufenthalts, in der Schweiz aufhält. Art. 115 Abs. 1 lit. b AuG gelangt nicht zur Anwendung, wenn es der betroffenen ausländischen Person - etwa aufgrund einer Weigerung des Heimatlands, Staatsangehörige zurückzunehmen oder Ausweispapiere auszustellen (vgl. <ref-ruling> E. 4.1.3; <ref-ruling> E. 2) - objektiv unmöglich ist, legal aus der Schweiz auszureisen bzw. rechtmässig in das Heimatland zurückzukehren. Das strafrechtliche Schuldprinzip setzt die Freiheit voraus, anders handeln zu können. Ein in der Schweiz illegal anwesender Ausländer darf daher nicht nach Art. 115 Abs. 1 lit. b AuG verurteilt werden, wenn ihm eine legale Ausreise aus der Schweiz objektiv nicht möglich ist (siehe dazu etwa Urteile 6B_274/2016 vom 15. Mai 2017 E. 1.6.1, zur Publikation vorgesehen; 6B_320/2013 vom 29. August 2013 E. 2.1; 6B_482/2010 vom 7. Oktober 2010 E. 3.2.2; je mit Hinweisen).
5.3.2. Das andauernde und ununterbrochene rechtswidrige Verweilen im Lande ist ein Dauerdelikt. Fehlt es nach einem ersten Schuldspruch für eine zweite Verurteilung an einem neuen Tatentschluss, ist bei der Strafzumessung darauf zu achten, dass die Summe der wegen des Dauerdelikts ausgesprochenen Strafen dem Gesamtverschulden angemessen ist und die im Gesetz angedrohte Höchststrafe nicht überschreitet (<ref-ruling> E. 4.2; Urteile 6B_715/2015 vom 21. März 2016 E. 2.6.1; 6B_819/2008 vom 26. Dezember 2008 E. 2.3). Die verurteilte Person kann sich nach der Rechtsprechung nicht nur im Zeitpunkt des Strafurteils (<ref-ruling> E. 4.2; Urteil 6B_819/2008 vom 26. Dezember 2008 E. 2.3), sondern auch im Rahmen einer Rückversetzung in den Strafvollzug nach <ref-law> darauf berufen, die Summe der bereits vollzogenen Freiheitsstrafe und der infolge Rückversetzung noch zu vollziehenden Freiheitsstrafe führe insgesamt zu einer nicht mehr angemessenen Strafe oder überschreite die Höchststrafe von Art. 115 Abs. 1 lit. b AuG (Urteil 6B_715/2015 vom 21. März 2016 E. 2.6.2). Die Rechtsprechung anerkennt damit, dass im Zusammenhang mit dem Straftatbestand von Art. 115 Abs. 1 lit. b AuG gewisse Fragen, welche an sich die Rechtmässigkeit der Schuldigsprechung und Bestrafung betreffen, ausnahmsweise auch im Rahmen einer Rückversetzung in den Strafvollzug nach <ref-law> zu prüfen sind.
5.4. Der Beschwerdeführer verlangt, bei der Frage der Rückversetzung in den Strafvollzug sei auch zu berücksichtigen, dass er sich des rechtswidrigen Aufenthalts in der Schweiz mangels Ausreisemöglichkeit gar nicht mehr strafbar machen könne.
Die Vorinstanz wird sich im Rahmen der Neubeurteilung mit der Frage befassen müssen, ob der Beschwerdeführer die Schweiz überhaupt verlassen kann (siehe dazu oben E. 4.3.2). Kommt sie dabei zum Schluss, diesem sei eine Ausreise aus der Schweiz objektiv nicht möglich, wird sie dies bei der Gesamtwürdigung im Rahmen der Prüfung der Rückversetzung des Beschwerdeführers in den Vollzug der Freiheitsstrafe wegen rechtswidrigen Aufenthalts nach Art. 115 Abs. 1 lit. b AuG zu berücksichtigen haben. Wohl sind die Strafbefehle vom 2. und 16. März 2012 mangels Einsprache in Rechtskraft erwachsen. Da der Beschwerdeführer erst im Jahre 2013 bei der Komorischen Botschaft vorsprach, ist nicht zu beanstanden, dass die Staatsanwaltschaft in diesen Strafbefehlen implizit davon ausging, diesem sei die Ausreise aus der Schweiz objektiv möglich. Stellt sich nachträglich jedoch heraus, dass dies nicht der Fall ist, ist dem zumindest bei der Frage der Rückversetzung in den Strafvollzug Rechnung zu tragen.
5.5. Die Vorinstanz nimmt im angefochtenen Entscheid keine Gesamtwürdigung der wesentlichen Umstände vor, sondern beschränkt sich auf den Hinweis, dem Beschwerdeführer könne angesichts seiner Vorstrafe und des teilweise bereits erfolgten Vollzugs einer Freiheitsstrafe keine günstige Prognose gestellt werden (angefochtenes Urteil E. 3.2 S. 24 unter Hinweis auf das erstinstanzliche Urteil E. 2.2 S. 24). Sie lässt namentlich auch unberücksichtigt, dass die neue Strafe unbedingt ausgesprochen wurde, was sich unter Umständen im Rahmen von <ref-law> auf die Prognose auswirken kann. Der Beschwerdeführer brachte bereits im vorinstanzlichen Verfahren vor, er mache derzeit eine Hormonbehandlung für eine Geschlechtsumwandlung (vgl. kant. Akten, Urk. 71 S. 13 und 18 f.; Urk. 75 S. 6 ff. und 19). Dass eine Person transsexuell ist und sich in einer Geschlechtsumwandlung befindet, steht nach der Rechtsprechung dem Vollzug einer Freiheitsstrafe nicht entgegen (vgl. Urteile 6B_606/2013 vom 27. September 2013; 6B_240/2012 vom 4. Dezember 2012 E. 2.4). Dennoch sind solche besonderen Umstände im Rahmen der Gesamtwürdigung und der Verhältnismässigkeitsprüfung auch bei der Frage der Rückversetzung in den Strafvollzug zu berücksichtigen, wenn es wie vorliegend lediglich noch um den Vollzug des Strafrests einer kurzen Freiheitsstrafe geht.
5.6. Die Beschwerde ist auch bezüglich der gerügten Rückversetzung in den Strafvollzug begründet.
6.
Die Beschwerde ist teilweise gutzuheissen und im Übrigen abzuweisen, soweit darauf eingetreten werden kann. Der Kanton Zürich hat den Beschwerdeführer im Umfang seines Obsiegens für das bundesgerichtliche Verfahren angemessenen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Da dieser um unentgeltliche Rechtspflege ersucht, ist die Entschädigung praxisgemäss seinem Rechtsvertreter zuzusprechen. Das Gesuch um unentgeltliche Rechtspflege wird in diesem Umfang gegenstandslos. Es ist zufolge Aussichtslosigkeit der Beschwerde abzuweisen, soweit der Beschwerdeführer unterliegt (<ref-law>). Seiner finanziellen Lage ist bei der Festsetzung der Gerichtskosten Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, das Urteil des Obergerichts des Kantons Zürich vom 25. Oktober 2016 teilweise aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen, soweit es nicht gegenstandslos geworden ist.
3.
Dem Beschwerdeführer werden Gerichtskosten von Fr. 600.-- auferlegt.
4.
Der Kanton Zürich hat Rechtsanwalt Pierre André Rosselet für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
5.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 14. Juli 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Unseld