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 <ref-law> 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.

Erwägungen:
1.
Gegen den angefochtenen Entscheid steht die Beschwerde in Strafsachen nach <ref-law> offen. Zwar handelt es sich um einen Zwischenentscheid; da er aber einen nicht wieder gutzumachenden Nachteil bewirken kann, ist die Beschwerde gemäss <ref-law> zulässig. Der Beschwerdeführer ist als direkter Adressat und vom Entscheid in seinen Rechten unmittelbar Betroffener zur Beschwerde legitimiert (<ref-law>).
2.
2.1. Nach <ref-law> ordnet die Verfahrensleitung über die Fälle der notwendigen Verteidigung hinaus dann eine amtliche Verteidigung an, wenn die beschuldigte Person nicht über die erforderlichen Mittel verfügt und die Verteidigung zur Wahrung ihrer Interessen geboten ist (vgl. <ref-ruling> E. 4.1). Zur Wahrung der Interessen der beschuldigten Person ist die Verteidigung namentlich geboten, wenn es sich nicht um einen Bagatellfall handelt und der Straffall in tatsächlicher oder rechtlicher Hinsicht Schwierigkeiten bietet, denen die beschuldigte Person allein nicht gewachsen wäre (<ref-law>). Ein Bagatellfall liegt jedenfalls dann nicht mehr vor, wenn eine Freiheitsstrafe von mehr als 4 Monaten, eine Geldstrafe von mehr als 120 Tagessätzen oder gemeinnützige Arbeit von mehr als 480 Stunden zu erwarten ist (<ref-law>).
2.2. Mit den gesetzlichen Bestimmungen von <ref-law> wurde die bisherige bundesgerichtliche Rechtsprechung zu <ref-law> und Art. 6 Ziff. 3 lit. c EMRK kodifiziert (<ref-ruling> E. 4.3; Urteil des Bundesgerichts 1B_448/2012 vom 17. Oktober 2012 E. 2.2; je mit Hinweisen). Wie sich aus dem Gesetzeswortlaut ("jedenfalls dann nicht") deutlich ergibt, sind die Nicht-Bagatellfälle (welche in der Bundesgerichtspraxis auch als "relativ schwer" bezeichnet werden) nicht auf die in <ref-law> beispielhaft genannten Fälle beschränkt. Bei der Prüfung, ob eine amtliche Verteidigung sachlich geboten ist, sind die konkreten Umstände des Einzelfalls zu berücksichtigen. Nach der bundesgerichtlichen Rechtsprechung kommt es bei der Frage, welche Sanktion der beschuldigten Person droht, nicht auf die abstrakte Strafobergrenze an, sondern auf die konkrete Sanktion, mit der die beschuldigte Person im Falle einer Anklageerhebung und Verurteilung zu rechnen hat. Eine bedürftige Partei hat Anspruch auf unentgeltliche Verbeiständung, wenn ihre Interessen in schwerwiegender Weise betroffen sind und der Fall in tatsächlicher und rechtlicher Hinsicht Schwierigkeiten bietet, die den Beizug eines Rechtsvertreters erforderlich machen. Falls das in Frage stehende Verfahren besonders stark in die Rechtsposition der betroffenen Person eingreift, ist die Bestellung eines unentgeltlichen Rechtsvertreters grundsätzlich geboten. Droht zwar ein erheblicher, nicht aber ein besonders schwerer Eingriff, müssen zur relativen Schwere des Eingriffs besondere tatsächliche oder rechtliche Schwierigkeiten hinzukommen, denen die betroffene Person - auf sich allein gestellt - nicht gewachsen wäre. Als besondere Schwierigkeiten, die eine Verbeiständung rechtfertigen können, fallen auch in der betroffenen Person liegende Gründe in Betracht, insbesondere deren Unfähigkeit, sich im Verfahren zurechtzufinden. Auch familiäre Interessenkonflikte oder mangelnde Schulbildung können massgebliche tatsächliche oder rechtliche Schwierigkeiten begründen (Urteil des Bundesgerichts 1B_170/2013 vom 30. Mai 2013 E. 4.3 mit vielen Hinweisen).
2.3. Gemäss der bundesgerichtlichen Rechtsprechung kann überdies das Prinzip der Waffengleichheit die Beiordnung eines amtlichen Verteidigers erfordern. Dieser Grundsatz ist als formales Prinzip schon dann verletzt, wenn eine Partei bevorteilt wird; es ist nicht notwendig, dass die Gegenpartei dadurch tatsächlich einen Nachteil erleidet. Das Bundesgericht leitet daraus etwa ab, dass ein Angeklagter jedenfalls dann Anspruch auf amtliche Verteidigung hat, wenn auch der geschädigten Person im Strafverfahren ein amtlicher Rechtsvertreter beigeordnet wird (Urteil des Bundesgerichts 1P.14/2005 vom 28. Februar 2005 E. 3.4, publ. in: Pra 2006 Nr. 2 S. 9; VIKTOR LIEBER, in: Donatsch/Hansjakob/Lieber [Hrsg.], Kommentar zur Schweizerischen Strafprozessordnung [StPO], 2010, N. 15 zu <ref-law>). Die Lehre fordert in einem allgemeineren Sinne, dass die Waffengleichheit eine amtliche Verteidigung des Beschuldigten gebiete, wenn andere Verfahrensbeteiligte verbeiständet sind ( HARARI/ALIBERTI, in: Kuhn/Jeanneret [Hrsg.], Commentaire romand, Code de procédure pénale suisse, 2011, N. 64 zu <ref-law>; NIKLAUS RUCKSTUHL, in: Niggli/Heer/Wiprächtiger [Hrsg.], Basler Kommentar zur Schweizerischen Strafprozessordnung, 2011, N. 36 zu <ref-law>; NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2009, N. 7 zu <ref-law>).
3.
3.1. Die Vorinstanz beurteilte den vorliegenden Fall weder als einen solchen der notwendigen Verteidigung noch als Bagatellfall, womit alle Verfahrensbeteiligten übereinstimmen. Es gibt keinen Anlass, von dieser Einschätzung abzuweichen. In tatsächlicher Hinsicht ist der Sachverhalt weitgehend erstellt und der Beschwerdeführer geständig. Er sieht darin allerdings offenbar kaum eine strafrechtliche Relevanz. In rechtlicher Hinsicht erscheint der vorliegende Fall denn auch nicht ohne Weiteres eindeutig. Im angefochtenen Entscheid wird jedenfalls nicht konkret ausgeführt, unter welche Strafnormen die Staatsanwaltschaft das Verhalten des Beschwerdeführers subsumiert. Angesichts der dafür bestehenden Möglichkeiten muss dieser aber ohnehin mit einer nicht unbedeutenden Strafe rechnen. Ob das für sich allein bereits für eine amtliche Verbeiständung genügen würde, kann offen bleiben. Hinzu kommt nämlich, dass die als Geschädigte am Strafverfahren beteiligte ehemalige Partnerin anwaltlich vertreten ist. Der nicht fachkundige und offenbar aus eher einfachen Verhältnissen stammende Beschwerdeführer steht daher nicht nur der fachlich ausgewiesenen Staatsanwaltschaft, sondern auch einer anwaltlich vertretenen Privatpartei gegenüber. Angesichts der bestehenden rechtlichen Unklarheiten erweist sich daher die Beiordnung eines amtlichen Anwalts aus Gründen der Waffengleichheit als geboten.
3.2. Der Beschwerdeführer hat Anspruch auf amtliche Verteidigung, sofern er nicht über genügend Mittel verfügt, seine Verteidigung selber zu finanzieren (<ref-law>). Obwohl das Obergericht im Kostenpunkt von bescheidenen finanziellen Verhältnissen aufseiten des Beschwerdeführers ausging, haben die Vorinstanzen dies nicht abschliessend abgeklärt. Es ist nicht Aufgabe des Bundesgerichts, das als erste Instanz zu tun. Die Sache ist daher an die Oberstaatsanwaltschaft zurückzuweisen, die das Gesuch des Beschwerdeführers um amtliche Verteidigung unter Berücksichtigung der bundesgerichtlichen Erwägungen neu zu prüfen haben wird.
4.
Die Beschwerde ist somit gutzuheissen, der angefochtene Entscheid des Obergerichts aufzuheben und die Sache an die Oberstaatsanwaltschaft zu neuem Entscheid zurückzuweisen. Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (<ref-law>). Hingegen hat der Kanton Zürich dem Beschwerdeführer für das bundesgerichtliche Verfahren eine angemessene Parteientschädigung auszurichten (<ref-law>). Damit wird das Gesuch um unentgeltliche Rechtspflege gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, der angefochtene Beschluss des Obergerichts des Kantons Zürich vom 7. Juni 2013 aufgehoben und die Sache zu neuem Entscheid an die Oberstaatsanwaltschaft des Kantons Zürich zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft IV, der Oberstaatsanwaltschaft und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 27. August 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Uebersax