Sachverhalt: A. Der aus dem Kosovo stammende X._ (geb. 1982) reiste im November 1991 im Rahmen des Familiennachzugs als Neunjähriger in die Schweiz ein, wo er die Niederlassungsbewilligung erhielt. Er lebte zunächst bei den Eltern in Winterthur/ZH und absolvierte die obligatorische Schulzeit. In der Folge fand er keine Lehrstelle und arbeitete in einer Eingliederungsschule und danach an einer Tankstelle. X._ wurde seit Februar 2000 mehrfach straffällig. Unter anderem verurteilte ihn die Bezirksanwaltschaft Winterthur/ZH mit Strafbefehl vom 12. September 2001 wegen Diebstahls, Sachbeschädigung und Hausfriedensbruchs zu bedingt aufgeschobenen drei Monaten Gefängnis und das Migrationsamt des Kantons Zürich sprach zudem eine Verwarnung aus. Das Bezirksamt Brugg/AG verurteilte X._ am 6. Mai 2003 wegen gewerbsmässigen, teilweise bandenmässigen Diebstahls, mehrfacher Sachbeschädigung, Hehlerei und mehrfachen Hausfriedensbruchs zu 15 Monaten Gefängnis, wobei ihm der bedingte Strafvollzug gewährt wurde; hingegen wurde der bedingte Strafvollzug für die dreimonatige Gefängnisstrafe widerrufen. Das Migrationsamt verwarnte ihn zudem erneut. Vom 8. Dezember 2003 bis 7. März 2004 befand sich X._ im Strafvollzug. In der Folge war er arbeitslos und besuchte einen Grundkurs im Lagerwesen, den er erfolgreich abschloss. Vom 6. Dezember 2004 bis 23. September 2005 befand sich X._ in Untersuchungshaft. Während der Haft kam am 18. Juni 2005 die Tochter A._ zur Welt. Nach der Haftentlassung arbeitete er als Lagerist und wohnte mit der Mutter des Kindes, Y._ (geb. 1987), einer serbischen Staatsangehörigen mit Niederlassungsbewilligung für den Kanton Zürich, zusammen. Mit Urteil vom 31. August 2007 verurteilte das Obergericht des Kantons Zürich X._ zweitinstanzlich wegen gewerbs- und bandenmässigen Diebstahls, mehrfacher Sachbeschädigung, mehrfachen Hausfriedensbruchs, Missbrauchs einer Datenverarbeitungsanlage und Gehilfenschaft zur Vereitelung einer Blutprobe zu zwei Jahren und acht Monaten Freiheitsstrafe. Vom 11. August 2008 bis zum 3. August 2009 befand er sich im Strafvollzug und am 4. November 2008 kam sein Sohn B._ zur Welt. Seine beiden Kinder verfügen über eine Niederlassungsbewilligung für den Kanton Zürich. B. Mit Verfügung vom 7. November 2008 widerrief das Migrationsamt des Kantons Zürich die Niederlassungsbewilligung von X._ und ordnete an, dieser habe das schweizerische Staatsgebiet unverzüglich nach Beendigung des Strafvollzugs zu verlassen. Hiergegen rekurrierte er erfolglos beim Regierungsrat des Kantons Zürich. Eine beim Verwaltungsgericht des Kantons Zürich eingereichte Beschwerde wurde von diesem mit Urteil vom 22. Juli 2009 teilweise gutgeheissen: in Bezug auf den Widerruf der Aufenthaltsbewilligung wurde die Beschwerde abgewiesen, in Bezug auf die Verweigerung der unentgeltlichen Rechtspflege dagegen gutgeheissen. C. Mit Eingabe vom 30. Juli 2009 erhebt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten sowie subsidiäre Verfassungsbeschwerde beim Bundesgericht. Er beantragt die Aufhebung des vorinstanzlichen Urteils (mit Ausnahme der Ziffer über die Gewährung der unentgeltlichen Rechtspflege); eventualiter sei ihm eine Aufenthaltsbewilligung zu erteilen. Subeventualiter sei die Unzumutbarkeit des Vollzugs der Wegweisung festzustellen und das Migrationsamt anzuweisen, beim Bundesamt für Migration die Anordnung einer vorläufigen Aufnahme zu beantragen. Weiter wird beantragt, dem Beschwerdeführer sei im Sinne einer vorsorglichen Massnahme der Aufenthalt und die Erwerbsaufnahme für die Dauer des Verfahrens zu bewilligen. Gerügt wird im Wesentlichen die Verletzung von Art. 8 EMRK und Art. 13 BV (Schutz des Familienlebens) sowie die Unverhältnismässigkeit des Widerrufs der Bewilligung. D. Der Regierungsrat des Kantons Zürich und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde, während das Verwaltungsgericht des Kantons Zürich auf eine Vernehmlassung verzichtet. E. Mit Verfügung vom 7. September 2009 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt, das Gesuch um weitere vorsorgliche Massnahmen dagegen abgewiesen.