Sachverhalt:
A.
Die Staatsanwaltschaft Zürich-Limmat stellte das Strafverfahren gegen A._ wegen Diebstahls mit Verfügung vom 8. November 2018 ein. Sie sprach diesem eine Genugtuung von Fr. 200.--, jedoch keine Entschädigung zu.
A._ gelangte dagegen mit Beschwerde an das Obergericht des Kantons Zürich, wobei er ein Schadenersatzbegehren über Fr. 3'200.-- stellte. Das Obergericht trat auf die Beschwerde infolge Verspätung mit Verfügung vom 21. Januar 2019 nicht ein.
B.
A._ beantragt mit Beschwerde in Strafsachen sinngemäss, der Entscheid vom 21. Januar 2019 sei aufzuheben und auf seine Beschwerde sei einzutreten.
C.
Das Obergericht und die Staatsanwaltschaft verzichteten auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, er habe die 10-tägige Beschwerdefrist eingehalten, da er seine Beschwerde innert dieser Frist der polnischen Post übergeben habe. Er sei weder in der Rechtsmittelbelehrung noch sonstwie darüber informiert worden, dass das Schreiben der Strafbehörde, der Post in der Schweiz oder einer diplomatischen Mission übergeben werden müsse.
1.2. Die Frist für die Beschwerde gemäss <ref-law> beträgt 10 Tage (<ref-law>). Die Frist beginnt am Tag nach der Mitteilung des angefochtenen Entscheids zu laufen (<ref-law>). Sie ist eingehalten, wenn die Beschwerde spätestens am letzten Tag der Frist bei der Strafbehörde abgegeben oder zu deren Handen der Schweizerischen Post, einer schweizerischen diplomatischen oder konsularischen Vertretung oder, im Falle von inhaftierten Personen, der Anstaltsleitung übergeben wurde (<ref-law>).
1.3. Die Einstellungsverfügung vom 8. November 2018 wurde dem (nicht anwaltlich vertretenen) Beschwerdeführer am 18. Dezember 2018 an seinem Wohnort in Polen zugestellt. Die 10-tägige Beschwerdefrist begann daher am 19. Dezember 2018 zu laufen und endete am 28. Dezember 2018. Der Beschwerdeführer übergab seine Beschwerde zwar am 27. Dezember 2018 der polnischen Post. Der Schweizerischen Post ging sie jedoch erst am 2. Januar 2019 zu (angefochtener Entscheid Ziff. 4 S. 2). Die Beschwerde war gemäss <ref-law> daher verspätet.
1.4.
1.4.1. Gleiche oder ähnliche Bestimmungen wie in <ref-law> sind auch in anderen Verfahrensgesetzen enthalten (vgl. <ref-law>, <ref-law>, <ref-law>, <ref-law>). Zu prüfen ist die in Lehre und Rechtsprechung aufgeworfene Frage, ob der Zustellungsempfänger bei einer Zustellung ins Ausland in der Rechtsmittelbelehrung oder auf andere Weise darauf hingewiesen werden muss, dass die Eingabe am letzten Tag der Frist der Schweizerischen Post übergeben werden muss und dass das Rechtsmittel fristwahrend auch bei einer schweizerischen diplomatischen oder konsularischen Vertretung im Ausland eingereicht werden kann.
1.4.2. Das Bundesgericht entschied in <ref-ruling> für das Sozialversicherungsrecht, die Verwaltung müsse die Gesetzesbestimmung von <ref-law> in der Rechtsmittelbelehrung wörtlich wiedergeben, um sich gegenüber einem im Ausland wohnhaften Versicherten auf die darin enthaltene Regel berufen zu können. Dies ergebe sich aus dem Grundsatz der Fairness und der Waffengleichheit (BGE, a.a.O., E. 4 S. 67 f.). Die Rechtsmittelbelehrung muss bei Verfügungsadressaten mit Wohnsitz im Ausland über die Vorschrift von <ref-law> hinaus demnach auch einen Hinweis auf die spezielle Bestimmung von <ref-law> betreffend die Fristwahrung enthalten. Gemäss dem Urteil 9C_755/2013 vom 11. Juli 2014 ist diese zu <ref-law> ergangene Rechtsprechung auch auf <ref-law> anwendbar (Urteil, a.a.O., E. 1). In einem jüngeren, amtlich publizierten Entscheid hielt das Bundesgericht zudem ausdrücklich an <ref-ruling> fest. Es erwog, selbst wenn angenommen würde, die Anforderungen von <ref-law> bräuchten nicht in der Rechtsmittelbelehrung selbst zu stehen, so müsste darauf in geeigneter Weise im Rahmen der Verfügungszustellung hingewiesen werden. Eine solche Informationspflicht sei zumindest gegenüber einer Adressatin der Verfügung im Ausland, die weder in erkennbarer Weise mit dem Schweizer Recht vertraut noch anwaltlich vertreten sei, zu bejahen (<ref-ruling> E. 3.2 S. 405).
Für das BGG (vgl. Art. 112 Abs. 1 lit. d und Art. 48 Abs. 1) wird die Frage in der Lehre kontrovers diskutiert (die Anwendbarkeit von <ref-ruling> bejahend: YVES DONZALLAZ, Loi sur le Tribunal fédéral, Commentaire, 2008, N. 1238 zu <ref-law>; anders AMSTUTZ/ARNOLD, in: Basler Kommentar, Bundesgerichtsgesetz, 3. Aufl. 2018, N. 10 zu <ref-law>, mit Hinweis auf die Letztinstanzlichkeit des bundesgerichtlichen Verfahrens; siehe dazu auch Urteile 1B_190/2012 vom 3. Juli 2012 E. 3; 4A_305/2010 vom 11. Oktober 2010; 2C_754/2008 vom 23. Dezember 2008 E. 2).
Wie die Frage für die StPO zu beurteilen ist, wurde soweit ersichtlich höchstrichterlich bisher nicht geklärt. NIKLAUS OBERHOLZER spricht sich als einer der wenigen Autoren, die sich überhaupt zu dieser Frage äussern, mit Verweis auf <ref-ruling> f. für eine um <ref-law> ergänzte Rechtsmittelbelehrung aus (vgl. NIKLAUS OBERHOLZER, Grundzüge des Strafprozessrechts, 3. Aufl. 2012, N. 1308).
1.4.3. Letzterem ist beizupflichten. Es sind keine Gründe ersichtlich, weshalb die in <ref-ruling> E. 4 entwickelte Rechtsprechung nicht zumindest auch für das kantonale Strafverfahren gelten soll. Urteile und andere verfahrenserledigende Entscheide müssen, sofern sie anfechtbar sind, eine Rechtsmittelbelehrung enthalten (<ref-law>). <ref-law> ist offen formuliert und äussert sich - anders als <ref-law> - nicht zum erforderlichen Inhalt der Rechtsmittelbelehrung. Die Bestimmung steht einer erweiterten Rechtsmittelbelehrung daher auch nicht entgegen. Die Rechtsmittelbelehrung soll die Parteien in die Lage versetzen, die ihnen von Gesetzes wegen zustehenden Rechtsmittel auch effektiv wahrzunehmen. Dies ist ohne Kenntnis des in <ref-law> geregelten Fristenlaufs u.U. nicht möglich. Angesichts der teils kurzen Fristen von 10 Tagen (vgl. <ref-law> für die Beschwerde; siehe auch <ref-law> für die Einsprache) und der Dauer der postalischen Zustellung in gewissen Staaten ist es zudem wichtig, dass die rechtsuchende Person auch über die Möglichkeit informiert ist, ihr Rechtsmittel im Ausland einer schweizerischen diplomatischen oder konsularischen Vertretung zu übergeben. Die Rechtsmittelbelehrung im Sinne von <ref-law> muss, wenn der Zustellungsempfänger im Ausland wohnhaft ist, grundsätzlich daher auch einen Hinweis auf <ref-law> enthalten.
1.4.4. Aus einer mangelhaften Eröffnung eines Entscheids dürfen den Parteien keine Nachteile erwachsen. Diese u.a. in <ref-law> verankerte Regel gilt auch für die StPO (NILS STOHNER, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2. Aufl. 2014, N. 3 zu <ref-law>). Sie entspricht einem allgemeinen Rechtsgrundsatz, der den verfassungsmässigen Vertrauensschutz sowie Art. 29 Abs. 1 und 2 BV konkretisiert (<ref-ruling> E. 3.1 S. 404 f.). Hatte der Rechtsuchende keine Kenntnis von der in <ref-law> verankerten Regel über den Fristenlauf bei einer Postaufgabe der Eingabe im Ausland, weil er darauf weder in der Rechtsmittelbelehrung noch auf andere Weise hingewiesen wurde, kann ihm diese Bestimmung nicht entgegengehalten werden. Dies entbindet ihn jedoch nicht von der Pflicht, das Rechtsmittel spätestens am letzten Tag der Frist der ausländischen Post zu übergeben.
1.5. Der nicht anwaltlich vertretene Beschwerdeführer übergab seine Beschwerde innert der 10-tägigen Beschwerdefrist der polnischen Post. Da die Rechtsmittelbelehrung keinen Hinweis auf <ref-law> enthielt, kann ihm die in dieser Bestimmung enthaltene Regel nach dem zuvor Gesagten nicht entgegengehalten werden. Anhaltspunkte, dass der Beschwerdeführer auf andere Weise auf die Bestimmung von <ref-law> aufmerksam gemacht wurde, liegen nicht vor. Die Vorinstanz trat auf die Beschwerde des Beschwerdeführers zu Unrecht nicht ein.
2.
Die Beschwerde ist gutzuheissen, die Verfügung vom 21. Januar 2019 aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Es werden keine Gerichtskosten erhoben (<ref-law>). Dem nicht anwaltlich vertretenen Beschwerdeführer ist keine Parteientschädigung zuzusprechen, da er keine besonderen Verhältnisse oder Auslagen geltend macht, die eine solche rechtfertigen könnten (vgl. <ref-ruling> E. 4b S. 207; <ref-ruling> E. 5b S. 519 f.). Dessen Gesuch um unentgeltliche Rechtspflege ist als gegenstandslos abzuschreiben.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Die Verfügung des Obergerichts des Kantons Zürich vom 21. Januar 2019 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 5. Juli 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Unseld