Sachverhalt: A. Der 1981 geborene türkische Staatsangehörige A._ reiste 1990 zusammen mit seiner Mutter und seinen Geschwistern zu seinem Vater in die Schweiz ein. Letzterer war damals als Angestellter des türkischen Konsulats in Zürich tätig. Der Aufenthalt von A._ wurde während der Erwerbstätigkeit des Vaters durch das Eidgenössische Departement für auswärtige Angelegenheiten (EDA) geregelt. Nachdem der Vater Ende Oktober 2004 seine Anstellung beim türkischen Konsulat aufgab, ersuchte A._ um erstmalige Erteilung einer ordentlichen Aufenthaltsbewilligung. Mit Verfügung vom 14. September 2007 wies das Migrationsamt des Kantons Zürich das Gesuch jedoch ab. Die von A._ hiergegen ergriffenen kantonalen Rechtsmittel blieben erfolglos: Letztinstanzlich wies das Verwaltungsgericht des Kantons Zürich seine Beschwerde mit Urteil vom 19. Mai 2010 ab. Dieses Urteil erwuchs in Rechtskraft. B. Am 10. November 2010 heiratete A._ eine 13 Jahre ältere deutsche Staatsangehörige, welche damals im Besitz einer Aufenthaltsbewilligung EG/EFTA war. Im Anschluss ersuchte er erneut um Erteilung einer Aufenthaltsbewilligung. Per 1. Oktober 2011 kehrte die Ehefrau des Beschwerdeführers indessen alleine nach Deutschland zurück; ihre Aufenthaltsbewilligung EG/EFTA erlosch am 28. Februar 2012. Mit Verfügung vom 28. November 2012 wies das Migrationsamt des Kantons Zürich das neuerliche Gesuch um Erteilung der Aufenthaltsbewilligung ab. Die von A._ hiergegen eingelegten kantonalen Rechtsmittel wurden von der Sicherheitsdirektion (Rekursentscheid vom 19. Februar 2013) sowie vom Verwaltungsgericht des Kantons Zürich (Urteil vom 26. Juni 2013) abgewiesen. Das Verwaltungsgericht verneinte dabei insbesondere, dass A._ aufgrund seiner ehelichen bzw. familiären Bindungen ein Rechtsanspruch auf Aufenthalt in der Schweiz zukomme und es verwies sodann auf strafrechtliche Verurteilungen sowie auf bestehende Betreibungen und Verlustscheine: - Mit Strafbefehl der Bezirksanwaltschaft Winterthur vom 14. Juni 2000 wurde A._ der Hehlerei schuldig gesprochen und zu sieben Tagen Gefängnis verurteilt; - Am 31. Mai 2001 sprach ihn die Bezirksanwaltschaft Zürich erneut der Hehlerei schuldig und bestrafte ihn mit 60 Tagen Gefängnis; - Mit Strafbefehl der Bezirksanwaltschaft Winterthur vom 1. Oktober 2004 wurde er sodann der Gehilfenschaft zu Freiheitsberaubung und Entführung sowie der Verfügung über mit Beschlag belegte Vermögenswerte schuldig befunden und zu einer Gefängnisstrafe von drei Monaten verurteilt; - Mit Verfügung vom 3. Oktober 2005 wandelte der Justizvollzug des Kantons Zürich insgesamt sechs Geldbussen von A._ in insgesamt 20 Tage Haft um. Am 30. Dezember 2005 verfügte der Justizvollzug überdies, dass insgesamt weitere 21 Tage Haft zufolge Bussenumwandlung zu verbüssen seien; - Mit Urteil vom 15. April 2010 sprach das Bezirksgericht Uster A._ der falschen Anschuldigung, der mehrfachen Verfügung über mit Beschlag belegte Vermögenswerte, des mehrfachen Fahrens in fahrunfähigem Zustand, der Entwendung eines Motorfahrzeugs zum Gebrauch sowie des Fahrens ohne Führerausweis schuldig und es bestrafte ihn mit einer Freiheitsstrafe von zehn Monaten; - Mit Strafbefehl vom 2. April 2012 wurde A._ von der Staatsanwaltschaft Winterthur/Unterland des Fahrens in fahrunfähigem Zustand, der Entwendung eines Motorfahrzeugs zum Gebrauch, des Führens eines Motorfahrzeugs mit abgelaufenem Führerschein auf Probe sowie der Übertretung des Betäubungsmittelgesetzes schuldig erklärt und zu einer Freiheitsstrafe von 180 Tagen verurteilt; - Von 2004 bis 2006 mussten gegen A._ Betreibungen in Höhe von rund Fr. 82'000.-- eingeleitet und Pfändungen in der selben Höhe vollzogen werden. Zudem bestanden im Oktober 2006 offene Verlustscheine von rund Fr. 49'500.--. C. Mit Eingabe vom 3. September 2013 führt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten sowie Verfassungsbeschwerde beim Bundesgericht. Er beantragt im Wesentlichen die Aufhebung des Urteils des Verwaltungsgerichts des Kantons Zürich vom 26. Juni 2013 sowie die Erteilung der Aufenthaltsbewilligung. Während die Sicherheitsdirektion und das Verwaltungsgericht des Kantons Zürich auf Vernehmlassung verzichten, schliesst das Bundesamt für Migration auf Abweisung der Beschwerde. 