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

Erwägungen:
1. 1.1 <ref-law> schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
1.2 Das streitige Gesuch um Verlängerung der Aufenthaltsbewilligung wurde vor Inkrafttreten des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) am 1. Januar 2008 eingereicht und beurteilt sich daher noch nach dem inzwischen aufgehobenen Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG) und seinen Ausführungserlassen (Art. 126 Abs. 1 AuG).
1.3 Gemäss Art. 17 Abs. 2 Satz 1 ANAG (in der Fassung vom 23. März 1990) hat der ausländische Ehegatte eines niedergelassenen Ausländers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, solange die Ehegatten zusammen wohnen.
Der Beschwerdeführer ist mit einer in der Schweiz niederlassungsberechtigten serbischen Staatsangehörigen verheiratet und lebt mit ihr zusammen. Damit steht ihm gestützt auf die erwähnte Bestimmung im Grundsatz ein Anspruch auf eine Aufenthaltsbewilligung zu. Ein analoger Anspruch besteht zudem aufgrund des in Art. 8 EMRK bzw. <ref-law> garantierten Rechts auf Achtung des Familienlebens, wenn - wie vorliegend die Ehefrau und die Kinder - nahe Angehörige über ein gefestigtes Anwesenheitsrecht (insbesondere die Niederlassungsbewilligung) in der Schweiz verfügen und die familiäre Beziehung tatsächlich gelebt wird und intakt ist (vgl. <ref-ruling> E. 3.1 S. 285 f.; <ref-ruling> E. 5.3.1 S. 211, je mit Hinweisen).
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten erweist sich damit als zulässig (<ref-law>).
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Die vom Beschwerdeführer neu geltend gemachten Tatsachen (u.a. angebliche Gefährdung im Heimatland, Vollzeit-Anstellung) und die eingereichten Unterlagen, welche die Zeit nach dem angefochtenen Urteil betreffen (u.a. verschiedene übersetzte Schriftstücke, Arbeitsvertrag vom 1. Mai 2009) bleiben als echte Noven im vorliegenden Verfahren daher unbeachtlich.
2. 2.1 Ein gemäss Art. 17 Abs. 2 ANAG bestehender Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung erlischt, wenn der Anspruchsberechtigte gegen die öffentliche Ordnung verstossen hat (Satz 4). Die betreffenden Voraussetzungen sind weniger streng als im Fall des ausländischen Ehegatten eines Schweizer Bürgers, in welchem ein Ausweisungsgrund im Sinne von Art. 10 ANAG vorliegen müsste. Die Verweigerung der Bewilligung muss jedoch verhältnismässig sein. Weil aber bereits geringere öffentliche Interessen für ein Erlöschen des Anspruches genügen, sind auch die privaten Interessen des betroffenen Ausländers weniger stark zu werten als bei einer Ausweisung (vgl. <ref-ruling> E. 4 S. 130 f.; <ref-ruling> E. 3a S. 390).
Eine vergleichbare Interessenabwägung setzt im Übrigen gemäss Art. 8 Ziff. 2 EMRK auch ein Eingriff in das Recht auf Achtung des Familienlebens voraus (<ref-ruling> E. 2 S. 5 f. mit Hinweisen). Unter diesem Gesichtswinkel ist namentlich zu fragen, ob den nahen Familienangehörigen zugemutet werden kann, dem Ausländer, der keine Bewilligung erhält, ins Ausland zu folgen. Die Zumutbarkeit der Ausreise für nahe Familienangehörige ist umso eher zu bejahen, als sein Verhalten seinen Aufenthalt in der Schweiz als unerwünscht erscheinen lässt. Eine allfällige Unzumutbarkeit der Ausreise ist mitabzuwägen, führt aber nicht für sich allein zur Unzulässigkeit einer Bewilligungsverweigerung (<ref-ruling> E. 4b S. 131).
2.2 Mit von Bedeutung ist vorliegend auch die so genannte, auf Ehegatten von Schweizerinnen zugeschnittene und für Ehegatten von Niedergelassenen verschärft zum Zuge kommende "Zweijahresregel", wonach einem Ausländer, der erstmals um eine Bewilligung ersucht oder nach bloss kurzer, ordnungsgemässer Aufenthaltsdauer deren Erneuerung beantragt, in der Regel selbst dann keine Bewilligung mehr erteilt wird, wenn dem Ehepartner die Ausreise un- oder nur schwer zumutbar ist. Es bedarf in solchen Fällen aussergewöhnlicher Umstände, um die Erteilung einer Aufenthaltsbewilligung noch zu rechtfertigen (sog. Reneja-Praxis, <ref-ruling>). Bei der Limite von zwei Jahren handelt es sich allerdings nur um einen Richtwert und nicht um eine feste Grenze (<ref-ruling> E. 4.1 S. 185 mit Hinweisen). Entscheidend kommt es auf die sich gegenüberstehenden Interessen an.
2.3 Der Beschwerdeführer hat sich in der Schweiz des gewerbsmässigen Betrugs und der mehrfachen Irreführung der Rechtspflege schuldig gemacht und wurde hiefür zu drei Jahren Zuchthaus, d.h. zu einer klar über dem oben erwähnten Richtwert liegenden Strafe, verurteilt. Der Strafrichter hat das Verschulden des Beschwerdeführers als schwer qualifiziert und seine kriminelle Energie als gross erachtet. Der Beschwerdeführer hat über Jahre hinweg das leidende Unfallopfer gemimt und den Sozialstaat schamlos ausgebeutet und dann mittels eines zweiten simulierten Verkehrsunfalls versucht, auch der Ehefrau zu einer IV-Rente zu verhelfen. Er hat durch seine strafrechtlichen Verfehlungen nicht bloss wiederholt gegen die öffentliche Ordnung verstossen (Art. 17 Abs. 2 ANAG), sondern sogar einen Ausweisungsgrund gesetzt (Art. 10 Abs. 1 lit. a ANAG). Entsprechend gewichtig erscheint das öffentliche Interesse, dem Beschwerdeführer den weiteren Aufenthalt in der Schweiz zu versagen.
2.4 Den öffentlichen Interessen sind im Rahmen der Verhältnismässigkeitsprüfung die privaten Interessen des Beschwerdeführers und seiner Angehörigen an einem Verbleib in der Schweiz gegenüberzustellen: Der Beschwerdeführer ist erst als Erwachsener (mit 22 Jahren) in die Schweiz gekommen. Er hat somit die gesamte Kindheit sowie die prägenden Jugendjahre in seinem Heimatland verbracht. Trotz verhältnismässig langem Aufenthalt ist er beruflich in der Schweiz nicht integriert. Nachdem er nur während sehr kurzer Zeit einer Erwerbstätigkeit nachgegangen war, bezog er von Februar 2001 bis März 2005 aufgrund seines inszenierten Unfalles und den simulierten Verletzungen und Beschwerden eine volle IV-Rente. Über besonders intensive soziale Beziehungen zum ausserfamiliären bzw. zum ausserhäuslichen Bereich in der Schweiz verfügt der Beschwerdeführer klarerweise nicht. Es kann davon ausgegangen werden, dass er mit den heimatlichen Verhältnissen nach wie vor bestens vertraut ist. Dies umso mehr, als er mehrheitlich Kontakte zu Landsleuten pflegt und sich zudem regelmässig besuchsweise nach Serbien begibt. Die Rückkehr in sein Heimatland, wo ein Grossteil seiner Familie lebt, ist folglich zumutbar.
Seine Ehefrau hält sich zwar schon länger in der Schweiz auf, aber sie stammt ebenfalls aus Serbien und verfügt weiterhin über Beziehungen zum Heimatland, wo ausser den Angehörigen ihres Ehegatten noch zwei Schwestern wohnen. Zudem ist ihr Leumund in der Schweiz getrübt: Sie wurde zusammen mit ihrem Ehemann straffällig und daher zu einer bedingten Gefängnisstrafe von 18 Monaten verurteilt. In der Folge wurde sie fremdenpolizeilich verwarnt. Ob unter diesen Umständen von einer der Aufenthaltsdauer entsprechenden guten Integration gesprochen werden kann, ist fraglich, kann aber dahingestellt bleiben. Sollte sich die Ehefrau entschliessen, die Schweiz mit ihrem Ehemann zu verlassen, wäre es ihr jedenfalls zuzumuten, ihm in das gemeinsame Heimatland zu folgen, dasselbe gilt für die Kinder, die noch in einem anpassungsfähigen Alter sind (vgl. <ref-ruling> E. 2 S. 67 f., 122 II 289 E. 2c S. 298). Die beiden jüngeren Kinder wurden im Übrigen gezeugt, als die Eheleute bereits nicht mehr damit rechnen konnten, weiterhin gemeinsam in der Schweiz leben zu können.
2.5 Aufgrund des Gesagten ist nicht zu beanstanden, dass das Verwaltungsgericht zum Schluss gekommen ist, das öffentliche Interesse an einer Nichtverlängerung der Aufenthaltsbewilligung des Beschwerdeführers überwiege dessen private und familiäre Interessen an einem Verbleiben in der Schweiz. Der Beschwerdeführer hat durch seine schweren strafrechtlichen Verfehlungen den Anspruch auf eine Aufenthaltsbewilligung gemäss Art. 17 ANAG verwirkt. Entsprechendes gilt auch für das aus Art. 8 EMRK ableitbare Aufenthaltsrecht. Ergänzend kann auf die Ausführungen im angefochtenen Entscheid verwiesen werden (<ref-law>).
3. 3.1 Die Beschwerde erweist sich somit als offensichtlich unbegründet und ist im vereinfachten Verfahren nach <ref-law> abzuweisen.
3.2 Bei diesem Verfahrensausgang wird der Beschwerdeführer kostenpflichtig (Art. 65 f. BGG). Eine Parteientschädigung ist nicht auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Sicherheitsdirektion, dem Regierungsrat und dem Verwaltungsgericht (2. Kammer) des Kantons Zürich sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 28. September 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Müller Dubs