Sachverhalt: A. X._ (geb. 1964) ist Staatsangehöriger von Bosnien und Herzegowina. Er heiratete 1985 eine in der Schweiz niedergelassene Bosnierin, reiste aber erst sechs Jahre später - im Jahr 1991- im Rahmen des Familiennachzugs in die Schweiz ein, worauf er hier eine Aufenthaltsbewilligung erhielt. Der Ehe entstammen fünf Kinder, die zwischen 1988 und 2000 geboren worden sind. X._ wurde in seinem Heimatland im Jahr 1986 wegen eines Tötungsdelikts zu einer Freiheitsstrafe von zehn Jahren und im Jahr 1988 wegen schwerer Körperverletzung zu einer solchen von sechs Monaten verurteilt. Diese Umstände waren den Schweizer Behörden zum Zeitpunkt der Erteilung der Aufenthaltsbewilligung nicht bekannt. Auch während seines ersten Aufenthaltes in der Schweiz erwirkte X._ verschiedene strafrechtliche Verurteilungen, namentlich 1995 wegen grober Verletzung der Verkehrsregeln (Busse von Fr. 500.--), 1998 wegen falscher Anschuldigung und mehrfacher Verletzung der Verkehrsregeln (ein Monat Gefängnis bedingt) sowie 2001 wegen Diebstahls, Sachbeschädigung, Hausfriedensbruchs und Entwendung eines Motorfahrzeugs zum Gebrauch (vier Monate Gefängnis bedingt). Nach der Verurteilung im Jahr 1998 wurde X._ zudem ausländerrechtlich verwarnt. Während eines Aufenthalts in seinem Heimatland im Jahr 2002 wurde X._ erneut verhaftet und wegen Raubes zu einer Freiheitsstrafe von vier Jahren und sechs Monaten verurteilt. Er bestreitet allerdings, dieses Delikt begangen zu haben und hält dafür, bei dem Prozess habe es sich um einen Racheakt der Angehörigen der von ihm im Jahr 1986 getöteten Person gehandelt. X._ hat beim Europäischen Gerichtshof für Menschenrechte (EGMR) wegen dieser erneuten Verurteilung ein Verfahren gegen den Staat Bosnien und Herzegowina angestrengt; die Angelegenheit ist beim EGMR noch hängig. Ausserdem erging gegen X._ im Jahr 2011 in Bosnien noch ein Strafurteil wegen unerlaubter Herstellung von Waffen oder explosivem Material und Handels damit. Die gegen ihn ausgesprochene Freiheitsstrafe betrug drei Monate. B. In Oktober 2011 reiste X._ wieder in die Schweiz ein und ersuchte um Erteilung einer neuen Aufenthaltsbewilligung. Im Juli 2012 wurde er hier wegen Verdachts des Einbruchdiebstahls verhaftet und bis August 2012 in Untersuchungshaft gesetzt. X._ hat diese Tat gestanden, doch liegt noch keine gerichtliche Beurteilung vor. Mit Verfügung vom 18. Februar 2013 wies das Zürcher Migrationsamt das Gesuch um Erteilung einer Aufenthaltsbewilligung ab. Die von X._ hiergegen ergriffenen kantonalen Rechtsmittel wurden von der Sicherheitsdirektion (Rekursentscheid vom 22. April 2013) und vom Verwaltungsgericht des Kantons Zürich (Urteil vom 10. Juli 2013) in der Hauptsache ebenfalls abgewiesen. C. Mit Eingabe vom 14. August 2013 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht und beantragt im Wesentlichen die Erteilung der Aufenthaltsbewilligung. Ausserdem ersucht er um die Gewährung der unentgeltlichen Rechtspflege und um Verbeiständung. Das Bundesamt für Migration sowie die Vorinstanz beantragen die Abweisung der Beschwerde. Mit Eingabe vom 2. Dezember 2013 nimmt X._ zum Vernehmlassungsergebnis Stellung.