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. 