Sachverhalt:
A.
X._ (geb. 1966) ist Staatsangehöriger Pakistans und gelangte 1991 als Asylsuchender in die Schweiz. 1992 verheiratete er sich mit der in der Schweiz niedergelassenen österreichischen Staatsangehörigen A._ (geb. 1942), worauf ihm - zu einem offenbar nicht mehr ermittelbaren Zeitpunkt - die Niederlassungsbewilligung erteilt wurde. Im Jahr 2004 trennten sich die Eheleute.
Seit geraumer Zeit pflegt X._ eine Beziehung zur italienischen Staatsangehörigen B._ (geb. 1976), wobei verschiedene Aspekte dieses Verhältnisses im kantonalen Verfahren umstritten geblieben sind. Ende Dezember 2012 hat B._ ein Kind geboren, das X._ am 28. Juni 2012 vorgeburtlich anerkannt hat.
B.
Im August 2007 wurde X._ wegen des Verdachts der Brandstiftung verhaftet und in Untersuchungshaft gesetzt. Diese dauerte rund ein Jahr; im August 2008 wurde er aus der Untersuchungshaft entlassen. Am 20. Januar 2012 verurteilte das Kriminalgericht des Kantons Luzern X._ rechtskräftig wegen Brandstiftung, versuchter Verursachung einer Explosion, versuchten Betrugs, gewerbsmässigen Betrugs, Betrugs und weiteren Delikten, alle begangen zwischen 2005 und 2007, zu einer Freiheitsstrafe von zwei Jahren und neun Monaten, wobei der Vollzug der Freiheitsstrafe im Umfang von 21 Monaten aufgeschoben wurde. In der Folge widerrief das Migrationsamt des Kantons Zürich die Niederlassungsbewilligung von X._ und wies ihn aus der Schweiz weg. Diese Anordnung bestätigte zunächst die Sicherheitsdirektion des Kantons Zürich mit Entscheid vom 18. September 2012 und kantonal letztinstanzlich das Verwaltungsgericht des Kantons Zürich mit Urteil vom 10. April 2013.
C.
X._ (Beschwerdeführer) erhebt gegen diesen Entscheid mit Eingabe vom 15. Mai 2013 beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt die Aufhebung des angefochtenen Urteils und die Rückweisung der Sache an das Verwaltungsgericht (Vorinstanz) zu neuer Beurteilung; eventuell sei das Migrationsamt zu verpflichten, vom Widerruf der Niederlassungsbewilligung abzusehen. Der Beschwerdeführer hat verschiedene Dokumente eingereicht, darunter eine Bestätigung hinsichtlich seines Wohnorts (von Herrn C._), eine Abstammungsuntersuchung eines humangenetischen Labors, worin festgehalten wird, dass er mit überwiegender Wahrscheinlichkeit der biologische Vater des Kindes von B._ ist, sowie dessen Geburtsschein.
Während das Verwaltungsgericht und die Sicherheitsdirektion auf eine Vernehmlassung verzichten, beantragt das Bundesamt für Migration die Abweisung der Beschwerde.
Mit Verfügung vom 24. Mai 2013 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den kantonal letztinstanzlichen Endentscheid betreffend den Widerruf einer Niederlassungsbewilligung ist zulässig (Art. 82 lit. a, Art. 83 lit. c [e contrario], Art. 86 Abs. 1 lit. d und Art. 90 BGG; Urteil 2C_926/2011 vom 12. Oktober 2012 E. 1 nicht publ. in: <ref-ruling> ff.; <ref-ruling> E. 1.2.1 S. 4). Der Beschwerdeführer ist durch den vorinstanzlichen Entscheid ausserdem besonders berührt (<ref-law>) und damit zur Anfechtung beim Bundesgericht befugt. Auf die form- und fristgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten ist einzutreten (vgl. Urteil 2C_828/2011 vom 12. Oktober 2012 E. 1 nicht publ. in: <ref-ruling> ff.).
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es legt seinem Urteil die Sachverhaltsfeststellungen der Vorinstanz zugrunde (<ref-law>), soweit diese nicht offensichtlich unrichtig, d.h. willkürlich sind (vgl. Urteil 2C_912/2012 vom 7. Juli 2013 E. 1.4 nicht publ. in: <ref-ruling> ff.; <ref-ruling> E. 4.1.2 S. 62; <ref-ruling> E. 1.2.2 S. 252; <ref-ruling> E. 7.1 S. 398) oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. Zudem ist vom Beschwerdeführer aufzuzeigen, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
1.3. Neue Tatsachen und Beweismittel dürfen ausserdem nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>; dazu <ref-ruling> E. 3.1.2 S. 122 f.; <ref-ruling> E. 2.1 S. 343 f.; je mit Hinweisen).
Die Bestätigung von Herrn C._, und ebenso die Abstammungsuntersuchung und der Geburtsschein, bleiben als Noven unberücksichtigt (zur Geburt des Kindes vgl. aber unten E. 2.3).
2.
Der Beschwerdeführer wirft der Vorinstanz zunächst vor, sie habe zu Unrecht ein gefestigtes, seit mehreren Jahren andauerndes Konkubinatsverhältnis zwischen ihm und B._ verneint. Bei rechtskonformer Ermittlung des Sachverhalts wäre offensichtlich gewesen, dass er sich auf Art. 8 EMRK und <ref-law> berufen könne. Damit rügt er eine offensichtlich unrichtige, d.h. willkürliche Sachverhaltsfeststellung durch das Verwaltungsgericht (<ref-law>; oben E. 1.2).
2.1. Nach der Rechtsprechung schützt Art. 8 EMRK im Zusammenhang mit der Bewilligung des Aufenthalts in erster Linie die Kernfamilie, d.h. die Gemeinschaft der Ehegatten mit ihren minderjährigen Kindern (<ref-ruling> E. 1.3.2 S. 146; <ref-ruling> E. 2 S. 14; <ref-ruling> E. 1d/aa S. 65). In den Schutzbereich von Art. 8 EMRK fallen aber auch nicht rechtlich begründete familiäre Verhältnisse, sofern eine genügend nahe, echte und tatsächlich gelebte Beziehung besteht; entscheidend ist die Qualität des Familienlebens und nicht dessen rechtliche Begründung (<ref-ruling> E. 3.1 S. 148). Das Bundesgericht hat hieraus abgeleitet, dass sich aus einem Konkubinat ein Bewilligungsanspruch dann ergibt, wenn die partnerschaftliche Beziehung seit Langem eheähnlich gelebt wird; die Beziehung der Konkubinatspartner muss bezüglich Art und Stabilität in ihrer Substanz einer Ehe gleichkommen. Dabei ist wesentlich, ob die Partner in einem gemeinsamen Haushalt leben; zudem ist der Natur und Länge ihrer Beziehung sowie ihrem Interesse und ihrer Bindung aneinander, etwa durch Kinder oder andere Umstände wie die Übernahme von wechselseitiger Verantwortung, Rechnung zu tragen (<ref-ruling> E. 3.1 S. 148; Urteile 2C_326/2013 vom 20. November 2013 E. 5.1; 2C_1026/2011 vom 23. Juli 2012 E. 4.3; 2C_702/2011 vom 23. Februar 2012 E. 3; Urteil der Grossen Kammer des EGMR Yigit gegen Türkei vom 2. November 2010 [Nr. 3976/05] §§ 93 und 96; vgl. auch Urteil Khan gegen Vereinigtes Königreich vom 12. Januar 2010, [47486/06] § 34 f. mit Hinweisen; vgl. GRABENWARTER/PABEL, Europäische Menschenrechtskonvention, 5. Aufl. 2012, S. 235 f. N. 16 zu § 22; Jens Meyer-Ladewig, EMRK, 3. Aufl. 2011, N. 49 zu Art. 8 EMRK).
2.2. Die Vorinstanz ist nicht von einem mehrjährigen Konkubinat des Beschwerdeführers mit B._ ausgegangen, das eine eheähnliche Beziehung darstellen und gestützt auf Art. 8 EMRK ein Anwesenheitsrecht begründen kann. Sie hat dies in erster Linie auf das Protokoll der polizeilichen Befragung vom 7. März 2012 abgestützt. Die darin angegebene Adresse handle sich nicht um den Wohnort von B._. Darüber hinaus habe der Beschwerdeführer im Protokoll eine andere, an dieser Adresse wohnhafte Person als seine "Logisgeberin" bezeichnet. Sodann werde in seiner Rekurseingabe (an die kantonale Sicherheitsdirektion) die selbe Adresse als seine Wohnadresse angegeben. Angesichts dessen sei davon auszugehen, dass er, wenn überhaupt, erst seit wenigen Monaten mit B._ zusammenlebe. Dies reiche für die Annahme eines eheähnlichen Konkubinats nicht aus.
Der Beschwerdeführer bestreitet nicht, polizeilich an der genannten Adresse angemeldet gewesen zu sein. Im August 2007 sei aber nicht nur dort, sondern auch an seinem "eigentlichen Wohnort" eine Haussuchung durchgeführt worden, nämlich am Wohnsitz von B._, an letzterer Adresse seien im Schlafzimmer eine Armbanduhr sowie eine Aktenmappe mit diversen Unterlagen von ihm sichergestellt worden, darunter Identitätsdokumente und Verträge. Diese Umstände deuteten klarerweise darauf hin, dass er bereits damals bei B._ gelebt habe.
Dass bei der Haussuchung vom August 2007 im Schlafzimmer der Wohnung von B._ wichtige und persönliche Effekten des Beschwerdeführers gefunden wurden, ergibt sich aus den Akten des gegen ihn geführten Strafverfahrens; auf diese hat sich auch die Vorinstanz berufen, weshalb sie kein unzulässiges Novum darstellen (vgl. oben E. 1.3). Der genannte Umstand lässt es als sehr wahrscheinlich erscheinen, dass die beiden bereits im August 2007 eine Beziehung von einer gewissen Intensität pflegten. Zuverlässige Aussagen darüber, ob diese die Qualität eines eheähnlichen (Konkubinats-) Verhältnisses erreichte, erlauben sie demgegenüber - entgegen der Ansicht des Beschwerdeführers - nicht. Zweifel an der Annahme eines eigentlichen Konkubinats - auch in einer ersten Phase nach der Entlassung aus der Untersuchungshaft im August 2008 - erwecken die von der Vorinstanz namhaft gemachten Aspekte (Adressbezeichnung in der Rekursschrift; Bezeichnung der an der angegebenen Adresse wohnhaften Frau C._ als seine "Logisgeberin").
2.3. Allerdings deuten weitere Sachverhaltselemente darauf hin, dass sich die Beziehung zu B._ intensiviert haben könnte. Der Vorinstanz war bekannt, dass B._ ein Kind erwartete, das der Beschwerdeführer vorgeburtlich anerkannt hatte und als dessen voraussichtlicher Geburtstermin der Januar 2013 errechnet worden war. Das Verwaltungsgericht hat hierzu festgehalten, ein ungeborenes Kind vermöge keine ausländerrechtlichen Ansprüche zu begründen. Es sei unklar, ob das Kind im Januar 2013 "tatsächlich (lebend) geboren wurde", und der Beschwerdeführer habe sich in seiner Eingabe vom Februar 2013 dazu nicht geäussert.
Nach der bundesgerichtlichen Rechtsprechung stellt ein gemeinsames Kind einen bedeutsamen Umstand dar, der eine nichteheliche Beziehung unter dem Blickwinkel von Art. 8 Ziff. 1 EMRK als relevant erscheinen lassen kann. Namentlich kann nach der Praxis - im Vergleich zu einer blossen Zweierbeziehung - bereits ein deutlich kürzeres Zusammenleben einen Bewilligungsanspruch gestützt auf Art. 8 EMRK auslösen, wenn das Paar ein gemeinsames Kind hat (oben E. 2.1). Darüber hinaus geht der EGMR von einem weiten Familienbegriff aus, der auch faktische Familienverhältnisse umfasst, die sich nicht auf eine Ehe abstützen (vgl. die Hinweise auf die Praxis im Urteil 2C_661/2010 vom 31. Januar 2011 E. 3). Die Vorinstanz hatte somit den Fall eines Ausländer zu beurteilen, der seit mindestens 5 1/2 Jahren eine Paarbeziehung mit einer hier niedergelassenen Ausländerin führte, seit einiger Zeit mit dieser zusammenlebte und mit ihr ein Kind hatte. Die Vorinstanz hätte deshalb abklären müssen, ob nicht unter diesen Aspekten eine relevante familiäre Beziehung vorliegt, zumal der Beschwerdeführer auch geltend gemacht hat, B._ und er beabsichtigten, die Ehe einzugehen.
2.4. Stattdessen hat das Verwaltungsgericht vage spekuliert, es sei unklar, ob das Kind tatsächlich lebend geboren worden sei. Die Möglichkeit einer Totgeburt war allerdings äusserst unwahrscheinlich, denn in der Schweiz ist die Zahl der Totgeburten im Vergleich zu den Lebendgeburten äusserst gering (weniger als 0,5 %); ein Umstand, der als allgemeinnotorisch gelten kann (zur Notorietät vgl. <ref-ruling> E. 4.1 S. 89 f.; vgl. Bundesamt für Statistik, Totgeburten und Säuglingssterblichkeit 2003-2010 Entwicklungen, Todesursachen und Risikofaktoren, erschienen am 20. März 2012 und abrufbar unter http://www.bfs.admin.ch/bfs/portal/de/index/news/publikationen.html?publicationID=4708). Bei ernstlichen Zweifeln an der (Lebend-) Geburt des gemeinsamen Kindes hätte die Vorinstanz den Beschwerdeführer im Rahmen seiner Mitwirkungspflicht zu einem entsprechenden Beweis auffordern können. Der Hinweis, dieser habe sich in seiner letzten Eingabe vom Februar 2013 nicht zu seiner Vaterschaft geäussert, verfängt nicht: Nachdem der Beschwerdeführer den Beweis der Schwangerschaft seiner Partnerin erbracht hatte, durfte er angesichts der soeben aufgezeigten Wahrscheinlichkeiten davon ausgehen, dass die Vorinstanz in ihren Erwägungen von der Geburt des Kindes ausgehen würde.
2.5. Angesichts dessen hat die Vorinstanz den Sachverhalt unvollständig festgestellt. Darin liegt eine Verletzung von Bundesrecht (<ref-law>; Urteile 2C_793/2012 vom 20. November 2012 E. 2.2; 2C_273/2010 vom 6. Oktober 2010 E. 1.3; 8C_33/2013 vom 13. Dezember 2013 E. 4.3.3; vgl. hierzu ULRICH MEYER, in: Niggli/Uebersax/ Wiprächtiger [Hrsg.], Basler Kommentar zum Bundesgerichtsgesetz, 2008, N. 25, 36 und 59 zu Art. 105; Hansjörg Seiler, in: Seiler/von Werdt/Güngerich [Hrsg.], Kommentar zum Bundesgerichtsgesetz, 2007, N. 24 zu Art. 97). Das Bundesgericht kann die erforderlichen sachverhaltlichen Feststellungen nicht selbst treffen. Die Sache ist demnach zur Ermittlung des rechtserheblichen Sachverhalts an das Verwaltungsgericht zurückzuweisen, namentlich der Qualität der Paarbeziehung zwischen dem Beschwerdeführer und B._ sowie zwischen diesem und seinem Kind, und zu anschliessendem neuem Entscheid.
2.6. Der Vollständigkeit halber sei darauf hingewiesen, dass das Vorliegen eines gefestigten, eheähnlichen Konkubinats und auch ein gemeinsames Kind nicht ohne weiteres zur Verlängerung der Niederlassungsbewilligung des Beschwerdeführers führen würde. Vielmehr wäre in einem zweiten Schritt zu prüfen, ob einer weiteren Anwesenheit nicht überwiegende öffentliche Interessen entgegen stehen würden.
3.
Die Beschwerde ist gutzuheissen und die Sache zur Ermittlung des rechtserheblichen Sachverhalts an das Verwaltungsgericht zurückzuweisen. Bei diesem Prozessausgang sind für das bundesgerichtliche Verfahren keine Gerichtskosten zu erheben (<ref-law>). Der Kanton Zürich hat dem Beschwerdeführer jedoch eine Parteientschädigung auszurichten (<ref-law>). Für die Neuregelung der Kosten- und Entschädigungsfolgen des kantonalen Verfahrens wird die Angelegenheit an das Verwaltungsgericht des Kantons Zürich zurückgewiesen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, das Urteil des Verwaltungsgericht des Kantons Zürich vom 10. April 2013 wird aufgehoben. Die Sache wird im Sinne der Erwägungen zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 23. Februar 2014
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Hänni