Sachverhalt:
A.
X._ stellte am 18. September 2012 in der Schweiz ein Asylgesuch, welches das damalige Bundesamt für Migration (BFM) mit Verfügung vom 7. November 2014 abwies. Die von X._ dagegen erhobene Beschwerde wies das Bundesverwaltungsgericht mit Urteil vom 19. Januar 2015 ab. Da X._ die Schweiz nach dem negativen Asylentscheid nicht verliess, verurteilte ihn die Staatsanwaltschaft Zürich-Limmat mit Strafbefehl vom 6. Juni 2016 wegen rechtswidrigen Aufenthalts zu einer bedingten Geldstrafe von 90 Tagessätzen zu Fr. 30.--, unter Ansetzung einer Probezeit von zwei Jahren.
Am 30. Mai 2017 wurde X._erneut einer Polizeikontrolle unterzogen, woraufhin die Staatsanwaltschaft Winterthur/Unterland gegen ihn am 31. Mai 2017 einen weiteren Strafbefehl wegen rechtswidrigen Aufenthalts erliess. X._ erhob dagegen Einsprache. In der Folge sprach ihn das Bezirksgericht Dielsdorf am 22. Januar 2018 des rechtswidrigen Aufenthalts im Sinne von Art. 115 Abs. 1 lit. b AuG schuldig und verurteilte ihn zu einer unbedingten Geldstrafe von 120 Tagessätzen zu Fr. 10.--. Es verzichtete auf den Widerruf der mit Strafbefehl der Staatsanwaltschaft Zürich-Limmat vom 6. Juni 2016 bedingt ausgesprochenen Geldstrafe von 90 Tagessätzen und verlängerte stattdessen die Probezeit von zwei Jahren um ein Jahr. X._ und die Staatsanwaltschaft erhoben gegen dieses Urteil im Strafpunkt Berufung.
Das Obergericht des Kantons Zürich stellte mit Urteil vom 14. September 2018 die Rechtskraft des erstinstanzlichen Schuldspruchs wegen rechtswidrigen Aufenthalts fest. Es bestrafte X._ mit einer unbedingten Freiheitsstrafe von vier Monaten und verzichtete in Bestätigung des erstinstanzlichen Urteils auf den Widerruf der am 6. Juni 2016 bedingt ausgesprochenen Vorstrafe.
B.
X._ beantragt mit Beschwerde in Strafsachen, das Urteil vom 14. September 2018 sei aufzuheben und er sei stattdessen mit einer angemessenen Geldstrafe von maximal 120 Tagessätzen zu Fr. 10.-- zu bestrafen, wobei ihm der bedingte Vollzug zu gewähren sei. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. X._ ersucht um unentgeltliche Rechtspflege.
C.
Das Obergericht und die Staatsanwaltschaft verzichteten auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, die Vorinstanz erachte die Voraussetzungen für den bedingten Vollzug der Strafe zu Unrecht als nicht erfüllt. Er macht dazu im Wesentlichen geltend, es sei von einer positiven Legalprognose auszugehen. Er habe sich - abgesehen von der Vorstrafe wegen rechtswidrigen Aufenthalts - seit seiner Einreise in die Schweiz im September 2012 in strafrechtlicher Hinsicht nichts zu Schulden kommen lassen. Aus dem Umstand, dass er am 26. Juni 2017 ein neues Asylgesuch gestellt habe, könne entgegen der Vorinstanz nicht auf einen renitenten Charakter geschlossen werden. Seit Einreichung des neuen Asylgesuchs halte er sich rechtmässig in der Schweiz auf. Sein Ausweis für Asylsuchende sei zuletzt bis Januar 2019 verlängert worden. Da er die Schweiz zurzeit nicht verlassen müsse, könne ihm nicht vorgehalten werden, dass er sich weigere, dies zu tun. Die Vorstrafe vom 6. Juni 2016 wegen rechtswidrigen Aufenthalts führe daher nicht zu einer negativen Legalprognose.
Der Beschwerdeführer argumentiert zudem, das Strafrecht dürfe nicht zur Durchsetzung der Wegweisung missbraucht werden. Um eine weggewiesene Person zum Verlassen der Schweiz anzuhalten, stünden den Migrationsbehörden Zwangsmassnahmen wie Ausschaffungs- oder Durchsetzungshaft zur Verfügung, welche nach der EU-Rückführungsrichtlinie strafrechtlichen Massnahmen vorzugehen hätten.
1.2. Art. 41 und 42 StGB wurden im Rahmen der am 1. Januar 2018 in Kraft getretenen Änderung des Sanktionenrechts revidiert. Anders als das alte Recht (vgl. aArt. 41 Abs. 1 und <ref-law>) sieht das neue Recht auch die kurze bedingte Freiheitsstrafe vor (nArt. 41 Abs. 1 und nArt. 42 Abs. 2 StGB). Da vorliegend eine kurze bedingte Freiheitsstrafe weder ausgesprochen noch beantragt wurde, sind die revidierten Bestimmungen für den Beschwerdeführer nicht milder. Mit der Vorinstanz ist daher von der Anwendbarkeit des alten Rechts auszugehen (vgl. <ref-law>; Urteile 6B_658/2017 vom 30. Januar 2018 E. 1.1; 6B_341/2017 vom 23. Januar 2018 E. 1.1), zumal der Beschwerdeführer dies nicht beanstandet.
1.3.
1.3.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 (a<ref-law>). Das Gericht kann auf eine Freiheitsstrafe von weniger als sechs Monaten nur erkennen, wenn die Voraussetzungen von aArt. 42 StGB für eine bedingte Strafe nicht gegeben sind und zu erwarten ist, dass eine Geldstrafe oder gemeinnützige Arbeit nicht vollzogen werden kann (aArt. 41 Abs. 1 StGB).
1.3.2. Im Rahmen von a<ref-law> genügt für den bedingten Vollzug das Fehlen einer ungünstigen Prognose. Der bedingte Strafaufschub 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 S. 186; <ref-ruling> E. 7.3 S. 117, 1 E. 4.2.2 S. 5 f.; je mit Hinweisen).
1.3.3. Die Prüfung der Bewährungsaussichten des Täters ist anhand einer Gesamtwürdigung aller wesentlichen Umstände vorzunehmen (<ref-ruling> E. 3.2 S. 282 f.; <ref-ruling> E. 4.4 S. 143, 1 E. 4.2.1 S. 5; je mit Hinweisen). In die Beurteilung miteinzubeziehen sind neben den Tatumständen namentlich 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 (<ref-ruling> E. 2.1 S. 185 f.; <ref-ruling> E. 4.2.1 S. 5). Einschlägige Vorstrafen sind bei der Prognosestellung erheblich zu gewichten; sie schliessen den bedingten Vollzug aber nicht notwendig aus (Urteile 6B_1070/2018 vom 14. August 2019 E. 5.2.3; 6B_154/2019 vom 26. April 2019 E. 1.3.2; 6B_254/2018 vom 6. September 2018 E. 1.2; je mit Hinweisen).
Dem Sachrichter steht bei der Prüfung der Prognose des künftigen Legalverhaltens ein Ermessensspielraum zu. Das Bundesgericht greift nur ein, wenn dieser sein Ermessen überschritten bzw. missbraucht und damit Bundesrecht verletzt hat (<ref-ruling> E. 3.1.1 S. 281; <ref-ruling> E. 4.2 S. 143 mit Hinweis).
1.3.4. Das Bundesgericht entschied im Zusammenhang mit Widerhandlungen gegen das Ausländergesetz, eine Vorstrafe wegen rechtswidrigen Verweilens im Land erlaube nicht die Stellung einer schlechten Prognose, wenn dem Beurteilten in der Zwischenzeit eine Aufenthaltsbewilligung erteilt worden sei und er sich mithin rechtmässig in der Schweiz aufhalte (BGE <ref-ruling> E. 7 S. 116 ff.). Gleiches gilt nach der Rechtsprechung, wenn die betroffene ausländische Person zwar über keine Aufenthaltsbewilligung verfügt, deren künftige Bestrafung wegen rechtswidrigen Aufenthalts jedoch ausgeschlossen wäre, weil es dieser - etwa aufgrund einer Weigerung des Heimatlands, Staatsangehörige zurückzunehmen oder Ausweispapiere auszustellen - objektiv unmöglich ist, legal aus der Schweiz auszureisen bzw. rechtmässig in das Heimatland zurückzukehren (Urteil 6B_118/2017 vom 14. Juli 2017 E. 3.2.4 und 5.3.1).
1.3.5. Da es vorliegend um eine Verurteilung wegen rechtswidrigen Aufenthalts geht, gelangt sodann die 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.) zur Anwendung. Nach der dazu ergangenen Rechtsprechung des Europäischen Gerichtshofs (EuGH) und des Bundesgerichts hat das verwaltungsrechtliche Rückführungsverfahren Vorrang vor strafrechtlichen Sanktionen. Eine Rückführungsrichtlinien-konforme Anwendung von Art. 115 Abs. 1 lit. b AuG verlangt, dass auf die Verhängung und den Vollzug einer Freiheitsstrafe verzichtet wird, wenn gegen den Betroffenen mit illegalem Aufenthalt ein Wegweisungsentscheid erging und die erforderlichen Entfernungsmassnahmen noch nicht ergriffen wurden. Die Verhängung einer Geldstrafe ist demgegenüber mit der Rückführungsrichtlinie nicht unvereinbar, vorausgesetzt sie erschwert das Verfahren der Entfernung nicht. Eine solche Sanktion kann unabhängig von den für die Umsetzung der Wegweisung erforderlichen Massnahmen ausgesprochen werden (<ref-ruling> E. 1.4.3 S. 204 f.; <ref-ruling> E. 1.9 S. 260 f.).
1.4. Die Vorinstanz stellt dem Beschwerdeführer eine ungünstige Legalprognose. Sie erwägt, diesem sei es schlicht egal gewesen, dass er die Schweiz nach der rechtskräftigen Abweisung seines ersten Asylgesuchs hätte verlassen müssen. Er habe die rechtskräftige Wegweisungsverfügung und die damit zusammenhängende Verurteilung wegen rechtswidrigen Aufenthalts im Juni 2016 einfach ignoriert, obwohl ihm bewusst gewesen sei, dass er sich illegal in der Schweiz aufhalte und diese zu verlassen habe. Er habe während dieser Zeit keinerlei Ausreisebemühungen unternommen und insbesondere nicht versucht, sich gültige Reisepapiere zu beschaffen. Aus dem Verhalten des Beschwerdeführers wie auch aus seinen Aussagen werde klar, dass er ungeachtet jedweder behördlichen Anordnung die Schweiz nicht verlassen und nicht in seine Heimat zurückkehren werde. Vor dem Hintergrund der einschlägigen Vorstrafe und der erneuten Delinquenz während der Probezeit sowie des offenkundig renitenten und uneinsichtigen Verhaltens des Beschwerdeführers sei von einer ungünstigen Legalprognose auszugehen. Daran ändere auch die Tatsache nichts, dass sich der Beschwerdeführer aufgrund des noch hängigen zweiten Asylverfahrens zurzeit und bis auf Weiteres legal in der Schweiz aufhalte und seine befristete Aufenthaltsgenehmigung bis am 2. Januar 2019 verlängert worden sei. Der Ausgang jenes Verfahrens sei nach wie vor völlig offen. Die abstrakte Möglichkeit der Erteilung einer Aufenthaltsbewilligung vermöge jedenfalls nichts daran zu ändern, dass sich der Beschwerdeführer grundsätzlich bereits seit Januar 2015 illegal in der Schweiz aufhalte, eine einschlägige Vorstrafe wegen rechtswidrigen Aufenthalts aufweise und sich seither offenkundig weigere, die Schweiz zu verlassen (angefochtenes Urteil S. 13-15).
1.5. Die Vorinstanz stellt dem Beschwerdeführer eine schlechte Legalprognose, weil dieser angab, er wolle nicht in seine Heimat zurückkehren. Er hoffe, in der Schweiz verbleiben zu können (angefochtenes Urteil S. 14). Der Beschwerdeführer hielt sich im Zeitpunkt des vorinstanzlichen Entscheids angesichts seines erneuten Asylgesuchs vom 26. Juni 2017 indes legal in der Schweiz auf. Daraus, dass er im Zeitpunkt des vorinstanzlichen Entscheids nicht bereit war, die Schweiz zu verlassen, ergibt sich daher noch keine Schlechtprognose. Dieser konnte im Zeitpunkt des vorinstanzlichen Entscheids gar nicht im Sinne von <ref-law> rückfällig werden (vgl. BGE <ref-ruling> E. 7; oben E. 1.3.4). Eine Gefahr, dass sich der Beschwerdeführer erneut nach <ref-law> wegen rechtswidrigen Aufenthalts strafbar macht, bestand nur für den Fall, dass das hängige Asylgesuch abgewiesen und ein erneuter Wegweisungsentscheid ergeht. Abgesehen von der Verurteilung wegen rechtswidrigen Aufenthalts hat der Beschwerdeführer keine Vorstrafen. Eine Rückfallgefahr für andere Straftaten besteht daher ebenfalls nicht.
Allerdings kann sich der Beschwerdeführer bloss auf ein vorübergehendes Aufenthaltsrecht für die Zeit des laufenden Asylverfahrens berufen. Ein behördlicher Entscheid, der das Aufenthaltsrecht des Beschwerdeführers materiell prüft und für die Zukunft bejaht, lag zumindest im Zeitpunkt des vorinstanzlichen Urteils nicht vor. Ob der Beschwerdeführer künftig in der Schweiz bleiben darf, ist daher noch offen. Auch wenn das zweite Asylgesuch des Beschwerdeführers vom 26. Juni 2017 ebenfalls abgewiesen werden sollte (bzw. zwischenzeitlich allenfalls bereits abgewiesen wurde), rechtfertigt es sich nach der Rechtsprechung jedoch nicht, gegenüber dem Beschwerdeführer eine Freiheitsstrafe zu verhängen, da die EU-Rückführungsrichtlinie für diesen Fall dem verwaltungsrechtlichen Rückführungsverfahren den Vorrang vor strafrechtlichen Sanktionen einräumt. Eine Freiheitsstrafe darf daher nur verhängt und vollzogen werden, wenn die erforderlichen Entfernungsmassnahmen bereits ergriffen wurden. Dem angefochtenen Entscheid kann nicht entnommen werden, dass gegenüber dem Beschwerdeführer in der Zeit nach der Abweisung seines ersten Asylgesuchs bis zu seinem zweiten Asylgesuch vom 26. Juni 2017 irgendwelche Entfernungsmassnahmen ergriffen wurden. Damit verstösst die von der Vorinstanz ausgesprochene unbedingte Freiheitsstrafe gegen Bundesrecht. Hinzu kommt, dass sich der Beschwerdeführer aufgrund seines zweiten Asylgesuchs seit Juni 2017 erneut längere Zeit legal in der Schweiz aufhielt. Im Falle einer Abweisung seines zweiten Asylgesuchs müssen grundsätzlich daher auch die neu zu ergreifenden Administrativmassnahmen zwecks Rückführung des Beschwerdeführers einer Freiheitsstrafe im vorliegenden Verfahren vorgehen. Zu berücksichtigen ist dabei auch, dass gemäss einer Medienmitteilung des Staatssekretariats für Migration (SEM) vom 16. Januar 2019 eine zwangsweise Rückführung nach Äthiopien seit 2018 möglich ist, da sich das Land im Februar 2018 gegenüber der EU und im November 2018 auch gegenüber der Schweiz verpflichtet hat, eigene Staatsangehörige ohne Aufenthaltsrecht in der Schweiz zurückzunehmen. Den Administrativbehörden stehen seit 2018 daher neue Möglichkeiten offen, um die Rückkehr nach Äthiopien gegen den Willen des Betroffenen zu erzwingen.
1.6. Heisst das Bundesgericht eine Beschwerde gut, so entscheidet es in der Sache selbst oder weist diese zu neuer Beurteilung an die Vorinstanz zurück (<ref-law>). Die Vorinstanz verfügt bei der Strafzumessung über ein erhebliches Ermessen, weshalb praxisgemäss kein reformatorischer Entscheid ergehen kann. Die Angelegenheit ist daher zur Neubeurteilung an die Vorinstanz zurückzuweisen. Auf den Antrag des Beschwerdeführers, es sei eine bedingte Geldstrafe von maximal 120 Tagessätzen zu Fr. 10.-- auszusprechen, kann daher nicht eingetreten werden.
2.
Die Beschwerde ist gutzuheissen, soweit darauf einzutreten ist. Es sind keine Kosten zu erheben (<ref-law>). Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Da dieser um unentgeltliche Rechtspflege ersucht, ist die Parteientschädigung praxisgemäss seinem Rechtsbeistand auszurichten. Das Gesuch um unentgeltliche Rechtspflege wird gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Das Urteil des Obergerichts des Kantons Zürich vom 14. September 2018 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Zürich hat Rechtsanwalt Nicolas von Wartburg 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, 27. September 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Unseld