Sachverhalt: A. X._ (geb. 1969) ist Staatsangehöriger der Republik Kosovo (vormals Serbien und Montenegro). Er heiratete 1989 in der gemeinsamen Heimat die Landsfrau Y._. Aus dieser Ehe gingen die Kinder A._ (geb. 1992) und B._ (geb. 1995) hervor. Die Ehe wurde am 21. November 1996 im Kosovo geschieden und das Sorgerecht dem Vater zugesprochen. Am 11. Dezember 1996 reiste dieser alleine in die Schweiz und ersuchte um Asyl. Mit Verfügung vom 9. April 1997 wies das damalige Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) das Gesuch ab und setzte X._ eine Ausreisefrist bis zum 31. August 1997. Diese Anordnung erwuchs in Rechtskraft. Am 27. August 1997 meldeten X._ und die Schweizer Bürgerin Z._ (geb. 1965), welche ursprünglich aus der Dominikanischen Republik stammt, das Eheversprechen an; die Trauung erfolgte am 17. Oktober 1997. In der Folge wurde X._ die Aufenthaltsbewilligung zum Verbleib bei der schweizerischen Ehefrau und nach fünf Jahren Ehedauer am 27. September 2002 die Niederlassungsbewilligung für den Kanton Zürich erteilt. Am 30. Juni 2004 wurde die Ehe X._ - Z._ auf gemeinsames Begehren vom Bezirksgericht Pfäffikon/ZH rechtskräftig geschieden. B. Am 5. Januar 2006 heiratete X._ in seiner Heimat erneut seine frühere Ehefrau Y._. Am 10. März 2006 stellte er beim Migrationsamt des Kantons Zürich das Gesuch um Familiennachzug für seine Ehefrau und die beiden Kinder. Am 15. Dezember 2006 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 14. Mai 2009 an das Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts vom 25. März 2009 und der Widerruf der Niederlassungsbewilligung seien aufzuheben. Eventualiter sei dem Beschwerdeführer die Aufenthaltsbewilligung zu erteilen. Gerügt wird die Verletzung von Art. 9 Abs. 4 lit. a (und Art. 7 Abs. 2) ANAG, die Verletzung des rechtlichen Gehörs (Art. 29 Abs. 2 BV) sowie eine offensichtlich unrichtige Sachverhaltsfeststellung. D. Der Regierungsrat und das Verwaltungsgericht des Kantons Zürich sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. E. Mit verfahrensleitender Verfügung vom 18. Mai 2009 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zuerkannt.