Sachverhalt:
A. Der serbische Staatsangehörige X._ (geb. 10. April 1965) reiste erstmals am 13. März 1990 in die Schweiz ein und hielt sich hier bis 1996 jeweils als Saisonnier auf. Am 23. Januar 1991 heiratete er im Heimatland die Landsfrau Y._ (geb. 1961). Aus dieser Ehe gingen zwei Töchter (geb. 1. Mai 1991 bzw. 19. August 1996) hervor.
Mit Urteil des Gemeindegerichtes in G._ (Serbien) vom 10. Dezember 1996 wurde die Ehe rechtskräftig geschieden und die beiden Kinder unter die elterliche Sorge der Mutter gestellt. Gleichentags heiratete X._ in G._ die Schweizer Bürgerin A._ (geb. 1954), worauf ihm am 13. März 1997 die Aufenthaltsbewilligung zum Verbleib bei der Ehefrau erteilt wurde. Am 25. Oktober 1999 gebar seine frühere Ehefrau den gemeinsamen Sohn B._. Am 10. Januar 2002 wurde X._ die Niederlassungsbewilligung erteilt. Drei Monate später trennten sich die Eheleute und mit Urteil des Bezirksgerichts M._ vom 15. Mai 2003 wurde die Ehe rechtskräftig geschieden. Am 20. August 2004 heiratete X._ im Heimatland erneut seine ehemalige serbische Ehefrau. Am 6. November 2006 und am 10. Mai 2007 stellte er beim Migrationsamt des Kantons Zürich Gesuche um Familiennachzug für seine serbische Ehefrau und die drei gemeinsamen Kinder.
B. Mit Verfügung vom 16. Oktober 2007 widerrief das Migrationsamt die Niederlassungsbewilligung von X._ und lehnte gleichzeitig die Gesuche um Bewilligung der Einreise seiner Ehefrau und Kinder ab.
Dagegen erhob X._ ohne Erfolg vorerst Rekurs an den Regierungsrat des Kantons Zürich und sodann Beschwerde an das Verwaltungsgericht des Kantons Zürich.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 11. September 2009 an das Bundesgericht beantragt X._, den Entscheid des Verwaltungsgerichts vom 8. Juli 2009 aufzuheben, ihm "weiterhin die Niederlassungsbewilligung zu erteilen" und den Familiennachzug zu bewilligen. Zudem ersucht er um Gewährung der unentgeltlichen Rechtspflege.
D. Das Verwaltungsgericht des Kantons Zürich verzichtet auf Vernehmlassung. Die Staatskanzlei des Kantons Zürich - im Auftrag des Regierungsrates - sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.

Erwägungen:
1. 1.1 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. Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121; in Kraft gewesen bis 31. Dezember 2007), das hier unbestrittenermassen noch anwendbar ist (vgl. Art. 126 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [AuG; SR 142.20]), entscheiden die zuständigen Behörden, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Es besteht damit grundsätzlich kein Anspruch auf Erteilung einer entsprechenden Bewilligung, es sei denn, der Ausländer oder seine in der Schweiz lebenden Angehörigen könnten sich auf eine Sondernorm des Bundesrechts (einschliesslich Bundesverfassungsrecht) oder eines Staatsvertrages berufen (<ref-ruling> E. 1.1 S. 3 f. mit Hinweisen).
1.2 Gegen Entscheide über den Widerruf oder die Feststellung des Erlöschens 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.
1.3 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (<ref-law>), setzt zudem voraus, dass die Behebung des Mangels sich für den Ausgang des Verfahrens als entscheidend erweist (<ref-law>).
2. 2.1 Gemäss Art. 7 Abs. 1 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung; des Weiteren hat er nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren Anspruch auf die Niederlassungsbewilligung. Kein Anspruch besteht, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern und namentlich jene über die Begrenzung der Zahl der Ausländer zu umgehen (Art. 7 Abs. 2 ANAG). Erfasst wird davon die sogenannte Scheinehe bzw. Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen (<ref-ruling> E. 2.1 S. 151 mit Hinweisen). Der Anspruch entfällt darüber hinaus auch bei rechtsmissbräuchlicher Berufung auf eine nur noch formell und ohne Aussicht auf Aufnahme bzw. Wiederaufnahme einer ehelichen Gemeinschaft bestehende Ehe (<ref-ruling> E. 2.2 S. 151 mit Hinweisen). Als eigenes und selbständiges Niederlassungsrecht erlischt die einmal erteilte Niederlassungsbewilligung nicht mit der Auflösung der Ehe. Sie kann aber widerrufen werden.
2.2 Nach Art. 9 Abs. 4 lit. a ANAG kann eine Niederlassungsbewilligung widerrufen werden, wenn der Ausländer sie durch falsche Angaben oder wissentliches Verschweigen wesentlicher Tatsachen erschlichen hat. Der Widerruf setzt voraus, dass der Betroffene wissentlich falsche Angaben gemacht oder wesentliche Tatsachen verschwiegen hat, in der Absicht, gestützt darauf den Aufenthalt oder die Niederlassung bewilligt zu erhalten. Nach Art. 3 Abs. 2 ANAG ist der Ausländer verpflichtet, der Behörde über alles, was für den Bewilligungsentscheid massgebend sein kann, wahrheitsgetreu Auskunft zu geben. Wesentlich sind dabei nicht nur Umstände, nach denen die Fremdenpolizei ausdrücklich fragt, sondern auch solche, von denen der Gesuchsteller wissen muss, dass sie für den Bewilligungsentscheid relevant sind. Das Erschleichen einer Niederlassungsbewilligung durch falsche Angaben oder durch wissentliches Verschweigen von Tatsachen kann schon darin liegen, dass die Angaben, auf welche sich die Behörden bei der seinerzeitigen Bewilligungserteilung gestützt hatten oder die bei späteren Verlängerungen der Aufenthaltsbewilligung oder bei der Erteilung der Niederlassungsbewilligung mangels anderer Angaben immer noch als massgebend betrachtet werden konnten, falsch oder unvollständig waren (Urteile 2C_311/2009 vom 5. Januar 2010 E. 2.2; 2C_33/2008 vom 7. Mai 2008 E. 3.2; 2A.33/2007 vom 9. Juli 2007 E. 4.1; 2A.129/2006 vom 27. Juni 2006 E.2.2; 2A.436/2003 vom 6. Januar 2004 E. 3.1; <ref-ruling> E. 3b S. 475 f.; je mit Hinweisen).
2.3 Das Verwaltungsgericht geht in seinem Entscheid von der dargestellten Rechtsprechung aus und hat diese korrekt angewandt.
Wenige Monate nach der Geburt seiner zweiten Tochter, die der Beschwerdeführer gezeugt hat, als er bereits seine zukünftige schweizerische Ehegattin kannte, liess er sich von seiner serbischen Ehefrau scheiden und heiratete am gleichen Tag seine schweizerische Freundin. Seit Beginn dieser Ehe führte er weiterhin eine eheähnliche Beziehung mit seiner früheren Ehefrau in Serbien. Aus dieser Parallelbeziehung ging im Jahre 1999 ein Sohn hervor. Damals kam es zu einer ersten Trennung des Beschwerdeführers und seiner schweizerischen Ehefrau. Spätestens drei Monate nach Erteilung der Niederlassungsbewilligung trennten sich die Ehegatten endgültig, und in der Folge wurde die Ehe geschieden. Der Beschwerdeführer heiratete darauf erneut seine frühere serbische Ehegattin und ersuchte um Nachzug seiner Familie in die Schweiz.
Aus dem zeitlichen Ablauf der Ereignisse ergibt sich eindeutig, dass der Beschwerdeführer nach einem aus zahlreichen Verfahren bekannten Verhaltensmuster (vgl. dazu etwa Urteile 2C_311/2009 vom 5. Januar 2010; 2C_33/2008 vom 7. Mai 2008 mit Hinweisen) planmässig vorgegangen ist, um sich in der Schweiz ein Anwesenheitsrecht zu verschaffen und seiner Familie den Nachzug zu ermöglichen. Ob eine Scheinehe vorliegt, kann trotz zahlreicher Indizien dahingestellt bleiben. Jedenfalls bestand die Ehe mit der schweizerischen Ehefrau schon lange vor Erteilung der Niederlassungsbewilligung nur formell und wurde vom Beschwerdeführer aufrecht erhalten zum alleinigen Zweck, die Erteilung der Niederlassungsbewilligung zu erwirken. Er beabsichtigte keineswegs, diese Ehe weiterzuführen, und hat die Behörden diesbezüglich jahrelang gezielt getäuscht. Selbst wenn die schweizerische Ehegattin den Beschwerdeführer aus Liebe geheiratet haben sollte, vermag dies nichts daran zu ändern, dass der Beschwerdeführer wissentlich wesentliche Tatsachen verschwiegen hat, um sich ein Anwesenheitsrecht zu verschaffen. Hätten die Fremdenpolizeibehörden von seinen tatsächlichen familiären Verhältnissen und seinen Plänen Kenntnis gehabt, wäre dem Beschwerdeführer die Niederlassungsbewilligung nicht erteilt worden. Die Voraussetzungen für deren Widerruf gemäss Art. 9 Abs. 4 lit. a ANAG sind somit erfüllt. Ergänzend kann auf die Erwägungen im angefochtenen Entscheid verwiesen werden (<ref-law>).
2.4 Der Widerruf der Niederlassungsbewilligung ist unter den gegebenen Umständen auch verhältnismässig. Zwar scheint der Beschwerdeführer zumindest beruflich integriert zu sein. Von einer eigentlichen Verwurzelung in der Schweiz kann jedoch nicht gesprochen werden. Der Beschwerdeführer lebte bis zum 25. Altersjahr in seiner Heimat und hat damit die prägenden Lebensjahre in Serbien verbracht. Seine relativ lange Aufenthaltsdauer in der Schweiz ist zudem insofern zu relativieren, als er sich davon gut sechs Jahre (1990-1996) als Saisonnier hier aufhielt und seine Anwesenheit in der Folge im Wesentlichen auf der Irreführung der Fremdenpolizei beruhte. Es darf davon ausgegangen werden, dass er mit den kulturellen und gesellschaftlichen Gepflogenheiten seines Heimatlandes nach wie vor bestens vertraut ist. Ins Gewicht fällt zudem, dass seine heutige Ehefrau und seine drei Kinder sowie weitere Verwandte dort leben. Dem Beschwerdeführer ist somit zuzumuten, in seine Heimat zurückzukehren.
3. 3.1 Der verfügte Widerruf der Niederlassungsbewilligung erweist sich als bundesrechtskonform. Ist die Niederlassungsbewilligung des Beschwerdeführers jedoch widerrufen, haben seine Ehefrau und seine Kinder weder gestützt auf Art. 17 Abs. 2 ANAG noch aufgrund von Art. 8 EMRK Anspruch auf Aufenthaltsbewilligung. Die Beschwerde ist somit als offensichtlich unbegründet im vereinfachten Verfahren nach <ref-law> abzuweisen, soweit darauf eingetreten werden kann.
3.2 Dem Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege kann sowohl mangels Begründung und Belege als auch wegen Aussichtslosigkeit der Beschwerdebegehren nicht entsprochen werden (<ref-law>). Der Beschwerdeführer wird somit kostenpflichtig (Art. 65 und 66 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, der Sicherheitsdirektion, dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 11. Februar 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Müller Dubs