Sachverhalt: A. Die Staatsanwaltschaft Zürich-Limmat verurteilte X._ mit Strafbefehl vom 13. Oktober 2014 wegen rechtswidrigen Aufenthaltes (Art. 115 Abs. 1 lit. b AuG) im Zeitraum vom 12. August 2014 bis am 12. Oktober 2014 zu einer bedingten Geldstrafe von 30 Tagessätzen zu je Fr. 30.--. Die Staatsanwaltschaft See/Oberland verurteilte ihn mit Strafbefehl vom 11. Juni 2015 wegen rechtswidrigen Aufenthaltes im Zeitraum vom 14. Oktober 2014 bis am 11. Juni 2015 und bestrafte ihn mit einer Geldstrafe von 50 Tagessätzen zu je Fr. 30.--. Die Strafe wurde in der Folge in eine Ersatzfreiheitsstrafe von 50 Tagen umgewandelt und im Umfang von zwei Dritteln vollzogen. Die Staatsanwaltschaft Zürich-Sihl verurteilte ihn mit Strafbefehl vom 12. Februar 2016 wegen rechtswidrigen Aufenthaltes im Zeitraum vom 11. August 2014 bis am 10. Februar 2016 sowie Verletzung der Mitwirkungspflicht bei der Beschaffung der Ausweispapiere (Art. 120 Abs. 1 lit. e AuG) zu einer unbedingten Freiheitsstrafe von 90 Tagen. Die Staatsanwaltschaft Winterthur/Unterland stellte das Verfahren wegen rechtswidrigen Aufenthaltes am 6. September 2017 ein. B. Mit Revisionsbegehren vom 9. Oktober 2017 gelangte X._ an das Obergericht des Kantons Zürich und verlangte die Aufhebung des Strafbefehls der Staatsanwaltschaft Zürich-Limmat vom 13. Oktober 2014, des Strafbefehls der Staatsanwaltschaft See/Oberland vom 11. Juni 2015 sowie des Strafbefehls der Staatsanwaltschaft Zürich-Sihl vom 12. Februar 2016. C. Das Obergericht des Kantons Zürich wies das Revisionsgesuch betreffend den Strafbefehl der Staatsanwaltschaft Zürich-Limmat vom 13. Oktober 2014 und den Strafbefehl der Staatsanwaltschaft See/ Oberland vom 11. Juni 2015 ab. Den Strafbefehl der Staatsanwaltschaft Zürich-Sihl vom 12. Februar 2016 hob es auf und wies das Verfahren zur Neubeurteilung an die Staatsanwaltschaft Zürich-Sihl zurück. D. X._ führt Beschwerde in Strafsachen. Er beantragt, die Abweisung des Revisionsgesuchs betreffend den Strafbefehl der Staatsanwaltschaft Zürich-Limmat vom 13. Oktober 2014 sowie den Strafbefehl der Staatsanwaltschaft See/Oberland vom 11. Juni 2015 und die genannten Strafbefehle seien aufzuheben. Die Strafverfahren betreffend rechtswidrigen Aufenthaltes der Staatsanwaltschaft Zürich-Limmat und der Staatsanwaltschaft See/Oberland seien einzustellen resp. er sei vom Vorwurf des rechtswidrigen Aufenthaltes freizusprechen. Eventualiter seien die zwei letztgenannten Strafverfahren zur neuen Behandlung an die Staatsanwaltschaften zurückzuweisen. Subeventualiter beantragt er, die Angelegenheit sei zur Durchführung eines ordnungsgemässen Verfahrens an das Obergericht zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung. E. Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich haben auf eine Vernehmlassung verzichtet. Das Bundesgericht hat die Angelegenheit am 24. April 2019 in einer öffentlichen Sitzung beraten.