Sachverhalt: A. Der aus Serbien stammende X._ (geb. 1972) heiratete im Januar 1994 in seiner Heimat seine Landsfrau Y._ (geb. 1972), die seit 1989 in der Schweiz lebt und über eine Niederlassungsbewilligung verfügt. Am 9. April 1994 reiste er im Rahmen des Familiennachzugs in die Schweiz ein, wo ihm eine Aufenthaltsbewilligung (zuletzt verlängert bis zum 8. Oktober 2005) erteilt wurde. Die vier aus der Ehe hervorgegangenen Kinder (geb. 1999, 2000, 2006 und 2007) besitzen die Niederlassungsbewilligung. B. X._ gab wiederholt zu Klagen Anlass: Mit Strafentscheid des Bezirksamts E._ vom 3. November 1995 wurde er wegen Entwendung zum Gebrauch und Fahrens ohne Führerschein mit einer Busse von Fr. 500.-- belegt. Das Bezirksamt F._ bestrafte ihn mit Strafentscheid vom 29. September 1997 wegen grober Verletzung der Verkehrsregeln mit einer Busse von Fr. 600.--. Am 8. Dezember 2004 wurde X._ verhaftet und in Untersuchungshaft versetzt. Mit Urteil des Bezirksgerichts G._ vom 24. November 2005 wurde er des gewerbsmässigen Betrugs im Sinn von Art. 146 Abs. 1 und 2 StGB und der mehrfachen Irreführung der Rechtspflege im Sinn von Art. 304 Ziff. 1 Abs. 1 StGB schuldig gesprochen und mit drei Jahren Zuchthaus bestraft sowie für die Dauer von sieben Jahren des Landes verwiesen. Zudem wurde er verpflichtet, der geschädigten Sozialversicherungsanstalt des Kantons Zürich Fr. 130'258.-- und, unter solidarischer Haftbarkeit mit Mitbestraften, zwei geschädigten Versicherungsgesellschaften Fr. 44'136.25 bzw. Fr. 17'970.-- zu bezahlen. Am 6. Dezember 2006 wurde X._ bedingt aus dem Strafvollzug entlassen, wobei die Probezeit auf drei Jahre angesetzt wurde. C. Mit Verfügung vom 11. Januar 2007 wies die Sicherheitsdirektion des Kantons Zürich (Migrationsamt) das Gesuch von X._ um Verlängerung der Aufenthaltsbewilligung ab und setzte ihm Frist zum Verlassen des zürcherischen Kantonsgebiets bis zum 15. April 2007. Dagegen rekurrierte X._ erfolglos an den Regierungsrat des Kantons Zürich. Mit Entscheid vom 25. Februar 2009 wies das Verwaltungsgericht des Kantons Zürich die gegen den Regierungsratsbeschluss erhobene Beschwerde ab. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 27. April 2009 beantragt X._, den Entscheid des Verwaltungsgerichts des Kantons Zürich vom 25. Februar 2009 aufzuheben und die Sicherheitsdirektion anzuweisen, X._ die Aufenthaltsbewilligung zu verlängern. Zudem stellt er das Gesuch, ihm für die Dauer des Beschwerdeverfahrens den Aufenthalt im Kanton Zürich zu bewilligen. Die Staatskanzlei des Kantons Zürich - für den Regierungsrat - und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. E. Mit Verfügung vom 30. April 2009 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde aufschiebende Wirkung zuerkannt.