Sachverhalt: A. Die Staatsanwaltschaft Zürich-Limmat führte gegen A._ eine Strafuntersuchung wegen Diebstahls, versuchten Diebstahls und Widerhandlungen gegen das Ausländergesetz (AuG; SR 142.20). Anlässlich der ersten polizeilichen Befragung am 3. Dezember 2014 verlangte A._ den "Anwalt der ersten Stunde". Der beigezogene Verteidiger stellte im Namen des Beschuldigten während der Einvernahme ein Gesuch um Bestellung als amtlicher Verteidiger. B. Mit Strafbefehl vom 4. Dezember 2014 wurde A._ wegen Diebstahls eines Fingerrings im Sinne von Art. 139 Ziff. 1 StGB und rechtswidriger Einreise gemäss Art. 115 Abs. 1 lit. a AuG schuldig gesprochen und mit einer Geldstrafe von 45 Tagessätzen zu je Fr. 30.-- bestraft. Der Vollzug der Geldstrafe wurde aufgeschoben, unter Ansetzung einer Probezeit von drei Jahren. Das Strafverfahren wegen versuchten Diebstahls einer Armbanduhr wurde mit Verfügung vom 8. Dezember 2014 eingestellt. Am 10. Dezember 2014 wies die Oberstaatsanwaltschaft des Kantons Zürich, Büro für amtliche Mandate, das Gesuch um Bestellung einer amtlichen Verteidigung ab. Die dagegen erhobene Beschwerde wies das Obergericht des Kantons Zürich am 5. Februar 2015 ab. C. Mit Beschwerde in Strafsachen vom 2. März 2015 an das Bundesgericht beantragt A._, der Beschluss des Obergerichts vom 5. Februar 2015 sei aufzuheben und ihm sei für das bei der Staatsanwaltschaft geführte Strafverfahren in der Person des Rechtsanwalts Patrick Iliev eine amtliche Verteidigung beizugeben und mit Fr. 1'201.40 (inkl. MwSt) zu entschädigen. Eventualiter sei die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. In prozessualer Hinsicht wird um unentgeltliche Prozessführung und Verbeiständung ersucht. Die Oberstaatsanwaltschaft schliesst auf Abweisung der Beschwerde. Die Staatsanwaltschaft Zürich-Limmat und das Obergericht verzichten auf eine Vernehmlassung. Der Beschwerdeführer hält in der Replik an seinen Anträgen fest. D. Das Bundesgericht hat die Angelegenheit am 12. August 2015 öffentlich beraten.