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.