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 <ref-law> (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.

Erwägungen:
1. 1.1 Das Bundesgericht prüft seine Zuständigkeit und die Zulässigkeit eines Rechtsmittels von Amtes wegen (<ref-law>; <ref-ruling>).
Nach <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Gegen Entscheide über den Widerruf einer Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig, weil grundsätzlich ein Anspruch auf das Fortbestehen dieser Bewilligung gegeben ist (<ref-ruling> E. 1.2.1 S. 4. mit Hinweis). Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde kann daher grundsätzlich eingetreten werden (vgl. jedoch E. 1.2 hiernach).
Die Verfassungsbeschwerde ist im Verhältnis zur Beschwerde in öffentlich-rechtlichen Angelegenheiten subsidiär (<ref-law>). Da hier die Letztere zur Verfügung steht, ist auf die von den Beschwerdeführern erhobene Verfassungsbeschwerde nicht einzutreten.
1.2 Nicht zulässig ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten dagegen insoweit, als der Beschwerdeführer subeventualiter beantragt, es sei die Unzumutbarkeit des Vollzugs der Wegweisung festzustellen und das kantonale Migrationsamt anzuweisen, beim Bundesamt für Migration die Anordnung einer vorläufigen Aufnahme zu beantragen, da dieser Antrag in den Bereich des Ausnahmekatalogs fällt (Art. 83 lit. c Ziff. 3 und 4 BGG).
Im Übrigen erweist sich der Subeventualantrag auch unter dem Blickwinkel der subsidiären Verfassungsbeschwerde als unzulässig, da die Rüge der Verletzung von verfassungsmässigen Rechten zu wenig substantiiert erhoben wird (vgl. <ref-law> und Art. 117 in Verbindung mit 106 BGG).
1.3 Mit der Beschwerde kann eine Rechtsverletzung nach Art. 95 und Art. 96 BGG geltend gemacht werden. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen vor Bundesgericht nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
1.4 Gemäss <ref-law> hat die Rechtsschrift die Begehren und deren Begründung zu enthalten. In der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Die Vorbringen müssen sachbezogen sein, damit aus der Beschwerdeschrift ersichtlich ist, in welchen Punkten und weshalb der angefochtene Entscheid beanstandet wird. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzt. Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.2 S. 254).
2. Mit Beschwerdeergänzung vom 31. August 2009 lässt der Beschwerdeführer dem Bundesgericht verschiedene Schriftstücke zukommen, namentlich einen Auszug aus dem Eheregister und einen Einsatzvertrag für eine Temporärfirma. Gemäss Eheregisterauszug haben der Beschwerdeführer und Y._ am 5. August 2009 die Ehe geschlossen.
Soweit diese Schriftstücke erst nach dem vorinstanzlichen Urteil vom 22. Juli 2009 datieren, was sowohl auf den Eheregisterauszug wie auf den Einsatzvertrag zutrifft, handelt es sich dabei um sog. "echte" Noven, welche im bundesgerichtlichen Verfahren in jedem Fall unzulässig sind (BGE 2C_295/2009 vom 25. September 2009 E. 3; <ref-ruling> E. 2.1 S. 343 f. mit Hinweisen). In dem Umfang, als die ins Recht gelegten Beweismittel bereits vor dem Entscheid des Verwaltungsgerichts entstanden sind, wurde vom Beschwerdeführer nicht dargelegt, inwiefern erst der angefochtene Entscheid zu deren Einreichung Anlass gegeben hätte. Auch diese Unterlagen können vom Bundesgericht mithin nicht berücksichtigt werden (<ref-law>; vgl. E. 1.3).
3. 3.1 Der von den Vorinstanzen angenommene Widerrufsgrund der Verurteilung zu einer längerfristigen Freiheitsstrafe gemäss Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. b des hier bereits anwendbaren Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) ist erfüllt, da gegen den Beschwerdeführer eine Freiheitsstrafe von mehr als einem Jahr ausgesprochen wurde (BGE 2C_295/2009 vom 25. September 2009 E. 4.2; zum Übergangsrecht vgl. Art. 126 AuG und Urteil 2C_745/2008 vom 24. Februar 2009 E. 1.2). Ob der von den Vorinstanzen ebenfalls bejahte Widerrufsgrund des schwerwiegenden Verstosses gegen die öffentliche Sicherheit und Ordnung nach Art. 63 Abs. 1 lit. b AuG gegeben ist, kann offen bleiben.
3.2 In jedem Fall rechtfertigt sich ein Widerruf bzw. die Nichtverlängerung der Bewilligung aber nur, wenn die jeweils im Einzelfall vorzunehmende Interessenabwägung die entsprechende Massnahme auch als verhältnismässig erscheinen lässt. Dabei sind namentlich die Schwere des Verschuldens, der Grad der Integration bzw. die Dauer der bisherigen Anwesenheit sowie die dem Betroffenen und seiner Familie drohenden Nachteile zu berücksichtigen (vgl. Art. 96 Abs. 1 AuG sowie Urteil 2A.451/2002 vom 28. März 2003 E.2, nicht publ. in: <ref-ruling>).
Die Notwendigkeit einer Verhältnismässigkeitsprüfung ergibt sich auch aus Art. 8 Ziff. 2 EMRK: Danach ist ein Eingriff in das von Art. 8 Ziff. 1 EMRK (resp. <ref-law>) geschützte Familienleben dann statthaft, wenn er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale oder öffentliche Sicherheit, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung oder zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesundheit und Moral sowie der Rechte und Freiheiten anderer notwendig erscheint. Bei der Interessenabwägung im Rahmen von Art. 8 Ziff. 2 EMRK sind die Schwere des begangenen Delikts, der seit der Tat vergangene Zeitraum, das Verhalten des Ausländers während dieser Periode, die Auswirkungen auf die primär betroffene Person sowie deren familiäre Situation zu berücksichtigen. Zudem sind die Dauer der ehelichen Beziehung und weitere Gesichtspunkte relevant, welche Rückschlüsse auf deren Intensität zulassen (Geburt und Alter allfälliger Kinder; Kenntnis der Tatsache, dass die Beziehung wegen der Straftat unter Umständen nicht in der Schweiz gelebt werden kann). Von Bedeutung sind auch die Nachteile, welche dem Partner oder den Kindern erwachsen würden, müssten sie dem Betroffenen in dessen Heimat folgen (BGE 2C_295/2009 vom 25. September 2009 E. 4.3 mit Hinweisen).
4. 4.1 Der Beschwerdeführer erachtet den Widerruf der Niederlassungsbewilligung als unverhältnismässig. Er führt aus, er habe keine höchstrangigen Rechtsgüter wie etwa Leib und Leben oder die sexuelle Integrität verletzt. Er habe sich zwischen seiner Entlassung aus der Untersuchungshaft und dem Antritt des Strafvollzugs nichts mehr zu Schulden kommen lassen und sich auch erfolgreich in die Arbeitswelt integriert. Die familiäre Situation habe ihn grundlegend verändert und er habe sich von seiner kriminellen Vergangenheit distanziert. Die angehäuften Schulden stünden grösstenteils im Zusammenhang mit seinem kriminellen Lebensabschnitt und er werde bestrebt sein, diese abzubauen. Eine Wegweisung in den Kosovo würde für ihn zu einer regelrechten Entwurzelung führen, da er über keinerlei Verwandte im Herkunftsland verfüge.
4.2 Die Einwendungen des Beschwerdeführers vermögen nicht zu überzeugen:
4.2.1 Der Beschwerdeführer wurde - neben einer Jugendstrafe - viermal strafrechtlich verurteilt, gesamthaft zu vier Jahren, zwei Monaten und zehn Tagen. Er unterbrach seine deliktische Tätigkeit im Wesentlichen nur, wenn er sich in Untersuchungshaft oder im Strafvollzug befand. Auch der Beschwerdeführer selber geht von einem schweren Verschulden aus. Er hat über Jahre banden- und gewerbsmässig delinquiert. Zwar mag es zutreffen, dass keine besonders schweren Gewalt-, Sexual- oder Betäubungsmitteldelikte begangen wurden. Hingegen liegen wiederholte Straftaten von erheblichem Gewicht vor und es besteht eine sich verschlechternde Situation, d.h. der Beschwerdeführer fuhr mit der deliktischen Tätigkeit fort und liess sich immer schwerere Taten zu Schulden kommen (Urteil 2C_745/2009 vom 24. Februar 2009 E. 4.2 mit Hinweisen). Bei dieser Sachlage durften die Vorinstanzen davon ausgehen, dass ein gewichtiges öffentliches Interesse besteht, den Beschwerdeführer von der Schweiz fernzuhalten.
4.2.2 Dem öffentlichen Interesse an einer Fernhaltung sind die privaten Gründe des Beschwerdeführers, in der Schweiz zu verbleiben, gegenüberzustellen.
Der Beschwerdeführer reiste 1991 im Alter von neun Jahren in die Schweiz ein und hält sich hier seit 19 Jahren auf. Wohl ist bei der Interessenabwägung zu berücksichtigen, dass er sich den überwiegenden Teil seines Lebens in der Schweiz aufgehalten hat. Je länger ein Ausländer in der Schweiz anwesend gewesen ist, desto strengere Anforderungen sind grundsätzlich an Fernhaltemassnahmen zu stellen. Jedoch ist eine Ausweisung bei wiederholter schwerer Straffälligkeit selbst dann nicht ausgeschlossen, wenn ein Ausländer hier geboren ist und sein ganzes bisheriges Leben in der Schweiz verbracht hat (<ref-ruling> E. 4.4.2 S. 190 mit Hinweisen).
Im vorliegenden Fall ist festzustellen, dass der Grad seiner Integration in die schweizerische Gesellschaft nicht mit seiner verhältnismässig langen Aufenthaltsdauer korrespondiert. Gemäss den verbindlichen Feststellungen der Vorinstanz (vgl. E. 1.3) pflegte der Beschwerdeführer - zumindest zur Zeit seiner kriminellen Aktivitäten - vorwiegend mit Landsleuten und Verwandten Kontakt. Ein neuer Freundeskreis besteht nicht. Eine vertiefte Integration in die hiesigen Verhältnisse und damit eine enge Verbundenheit zur Schweiz ist nicht ersichtlich, weshalb der vom Beschwerdeführer angerufenen langen Aufenthaltsdauer kein allzu hohes Gewicht beizumessen ist.
In Bezug auf die Prognose für das künftige Wohlverhalten, welche im Lichte des gesamten ausländerrechtlich relevanten Verhaltens und nicht lediglich aufgrund der Zeitspanne seit der (letzten) Haftentlassung zu stellen ist, dürfen strengere Massstäbe angelegt und einem korrekten Verhalten im Strafvollzug bzw. seit der bedingten Entlassung geringere Bedeutung beigemessen werden als bei den entsprechenden strafrechtlichen Entscheiden (Urteil 2A.51/2006 vom 8. Mai 2006 E. 4.2.3 mit Hinweisen). Die im Vollzugsbericht für den Beschwerdeführer gestellte günstige Prognose ist deshalb zu relativieren und namentlich in Bezug zur jahrelangen deliktischen Tätigkeit (mit Verurteilungen zu insgesamt über 50 Monaten Freiheitsstrafe) zu setzen. Zu Recht hat die Vorinstanz in diesem Zusammenhang auch festgehalten, dass ihn die Beziehung zu seiner damaligen Freundin und heutigen Ehefrau und seine beruflichen Tätigkeiten nicht von seinen deliktischen Aktivitäten abzuhalten vermochten.
Die Vorinstanz hat weiter festgestellt, dass der Beschwerdeführer Albanisch in Wort und Schrift beherrscht, einen Teil seiner Kindheit im Kosovo verbracht und das Land auch nach seiner Einreise in die Schweiz wieder besucht hat. Zwar mag es zutreffen, dass die wirtschaftliche Situation im Kosovo schwieriger und die Arbeitslosenquote erheblich höher ist als in der Schweiz und eine Rückkehr in sein Heimatland den Beschwerdeführer damit hart treffen würde. Diese Folge ist jedoch seinem kriminellen Verhalten zuzuschreiben und deshalb hinzunehmen. Damit durfte die Vorinstanz den Schluss ziehen, dass keine massgeblichen Gründe, die der Wiedereingliederung des Beschwerdeführers in seiner Heimat entgegenstünden, ersichtlich sind.
4.2.3 Soweit sich der Beschwerdeführer weiter auf Art. 8 EMRK und <ref-law> (Recht auf Achtung des Privat- und Familienlebens) beruft, kann seiner Rüge nicht gefolgt werden. Zwar wird die Beziehung zu seinen beiden Kindern und seiner damaligen Freundin und heutigen Ehefrau unbestrittenermassen vom Schutzbereich der genannten Bestimmungen erfasst. Die Vorinstanz durfte aber zu Recht davon ausgehen, dass eine Ausreise sowohl für die heutige Ehefrau wie für die gemeinsamen Kinder nicht unverhältnismässig wäre. Art. 8 EMRK und <ref-law> gelten nicht absolut: Es ergibt daraus weder ein Recht auf Aufenthalt in einem bestimmten Staat noch auf die Wahl des für das Familienlebens am geeignetsten erscheinenden Orts (<ref-ruling> E. 3.1 S. 285). Die Ausreise wäre für die Ehefrau und die Kinder zwar mit Nachteilen verbunden. Die Ehefrau ist aber mit den Verhältnissen im Kosovo vertraut und hat gemäss den Feststellungen der Vorinstanz dort Verwandte. Dazu kommt, dass ihr das deliktische Verhalten ihres damaligen Freundes und heutigen Ehemannes schon zum Zeitpunkt der ersten Schwangerschaft bekannt sein musste. Die beiden Kinder sind zudem noch in einem anpassungsfähigen Alter, so dass es zumutbar erscheint, dass diese dem ausgewiesenen Elternteil folgen (<ref-ruling> E. 2b S. 67). Der Ehefrau und den Kindern steht es im Übrigen frei, ob sie im Rahmen ihrer Niederlassungsbewilligung in der Schweiz verbleiben oder ihrem Ehemann und Vater in den Kosovo folgen wollen.
4.2.4 Zusammenfassend ist es bei dieser Sachlage nicht zu beanstanden, wenn die Vorinstanz annimmt, dass das öffentliche Interesse an einer Fernhaltung des Beschwerdeführers höher zu gewichten ist als dessen persönliche Interessen an seinem Verbleib in der Schweiz. Das Verwaltungsgericht hat mithin die Verhältnismässigkeit des Widerrufs der Niederlassungsbewilligung des Beschwerdeführers zu Recht bejaht. Dem Beschwerdeführer kann auch nicht im Sinne einer milderen Massnahme eine Aufenthaltsbewilligung erteilt werden, da damit das angestrebte Sicherheitsziel - die Entfernung des Beschwerdeführers aus der Schweiz - nicht erreicht werden könnte.
5. Damit erweist sich die Beschwerde in öffentlich-rechtlichen Angelegenheiten als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer grundsätzlich kostenpflichtig (<ref-law>). Er hat jedoch um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung für das bundesgerichtliche Verfahren ersucht. Die von ihm gestellten Rechtsbegehren können - wie bereits die Vorinstanz zu Recht ausgeführt hat - insbesondere mit Blick auf die lange Anwesenheitsdauer in der Schweiz und seine familiäre Situation nicht als von vorneherein aussichtslos bezeichnet werden. Die Bedürftigkeit des Beschwerdeführers ist ebenfalls zu bejahen. Dem Gesuch ist daher zu entsprechen. Damit sind keine Gerichtskosten zu erheben (<ref-law>) und der Vertreter des Beschwerdeführers wird für das bundesgerichtliche Verfahren als unentgeltlicher Rechtsbeistand eingesetzt (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen:
3.1 Es werden keine Kosten erhoben.
3.2 Rechtsanwalt Bernhard Jüsi, Zürich, wird für das bundesgerichtliche Verfahren als unentgeltlicher Rechtsbeistand eingesetzt und aus der Bundesgerichtskasse mit Fr. 1'500.-- entschädigt.
4. Dieses Urteil wird dem Beschwerdeführer, der Sicherheitsdirektion, dem Regierungsrat und dem Verwaltungsgericht, 4. Kammer, des Kantons Zürich, sowie dem dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 26. Januar 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Winiger