Sachverhalt: A. A.a. Gegen X._ läuft eine Strafuntersuchung wegen Stalkings. Insbesondere soll er seiner ehemaligen Partnerin gegen deren ausdrücklichen Wunsch unzählige SMS und Briefe mit teilweise sexuellem Inhalt geschrieben und sich an deren Arbeitsort telefonisch nach ihr erkundigt haben. Sie fühlte sich auch durch den im gleichen Haus wohnhaften Beschuldigten beobachtet und kontrolliert. A.b. Am 13. März 2013 wies das Büro für amtliche Mandate der Oberstaatsanwaltschaft des Kantons Zürich ein Gesuch von X._ um Bestellung eines amtlichen Verteidigers ab. Mit Beschluss vom 7. Juni 2013 wies das Obergericht des Kantons Zürich eine dagegen erhobene Beschwerde ab. B. Mit Beschwerde in Strafsachen vom 26. Juni 2013 an das Bundesgericht beantragt X._, den Beschluss des Obergerichts aufzuheben und seinen Rechtsvertreter als amtlichen Verteidiger für das Strafverfahren zu bestellen. Zur Begründung wird im Wesentlichen ein Verstoss gegen Art. 132 StPO geltend gemacht. In prozessualer Hinsicht wird um Erteilung der unentgeltlichen Rechtspflege und Verbeiständung ersucht. C. Die das Verfahren inzwischen leitende Staatsanwaltschaft IV, die für die Beiordnung der amtlichen Verteidigung zuständige Oberstaatsanwaltschaft sowie das Obergericht des Kantons Zürich haben alle auf eine Stellungnahme verzichtet. 