Sachverhalt: A. Der serbische Staatsangehörige X._, geb. 1955, hat aus erster Ehe mit einer Landsfrau zwei heute volljährige Kinder. Am 18. Februar 2004 heiratete er die in der Schweiz niedergelassene A._ (geb. 1980), worauf ihm die Aufenthaltsbewilligung für den Kanton Zürich erteilt wurde. In der Folge stellte sich heraus, dass gegen X._ in Deutschland verschiedene Strafurteile ergangen sind. So wurde er unter anderem, nachdem er 2001 von der Schweiz an Deutschland ausgeliefert worden war, am 18. Februar 2002 vom Landgericht Bielefeld wegen Vergewaltigung und Betrug zu einer Freiheitsstrafe von drei Jahren und drei Monaten verurteilt. Nach Entlassung aus dem Strafvollzug im Mai 2003 wurde er aus der BRD ausgewiesen und in sein Heimatland abgeschoben. Weil er im Gesuch um Erteilung der Aufenthaltsbewilligung wahrheitswidrig angegeben hatte, weder in der Schweiz noch im Ausland vorbestraft zu sein, wurde X._ am 4. November 2004 vom Stadtrichter von Zürich wegen Zuwiderhandlung gegen fremdenpolizeiliche Vorschriften mit einer Busse von Fr. 500.-- bestraft. B. Mit Blick auf die genannten Umstände verweigerte die Direktion für Soziales und Sicherheit des Kantons Zürich, Migrationsamt, X._ mit Verfügung vom 5. November 2004 die Verlängerung der Aufenthaltsbewilligung. Dagegen rekurrierte der Betroffene erfolglos an den Regierungsrat des Kantons Zürich (Entscheid vom 14. Dezember 2005). Auf eine hiegegen erhobene Beschwerde trat das Verwaltungsgericht des Kantons Zürich am 12. Juli 2006 unter anderem aufgrund eines veränderten Sachverhalts nicht ein: Im Dezember 2005 hatte sich X._ in seiner Heimat von seiner zweiten Ehefrau scheiden lassen und am 26. April 2006 die Schweizer Bürgerin B._ (geb. 1968) geheiratet, um sich nunmehr im fremdenpolizeilichen Verfahren auf diese Ehe zu berufen. C. Mit Verfügung vom 15. Januar 2007 wies das Migrationsamt das am 3. Mai 2006 von X._ eingereichte Gesuch um Erteilung einer Aufenthaltsbewilligung zum Verbleib bei seiner Schweizer Ehefrau ab. Gegen diese Verfügung legte X._ erfolglos Rekurs beim Regierungsrat ein (Beschluss vom 19. Dezember 2007). Mit Entscheid vom 16. April 2008 wies das Verwaltungsgericht des Kantons Zürich, 4. Kammer, eine hiegegen gerichtete Beschwerde ab. D. Mit Eingabe vom 5. Juni 2008 erhebt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, den Entscheid des Verwaltungsgerichts vom 16. April 2008 aufzuheben und dem Gesuch um Erteilung resp. Verlängerung der Aufenthaltsbewilligung stattzugeben. Die Staatskanzlei (im Auftrag des Regierungsrates) des Kantons Zürich und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich (4. Kammer) verzichtet auf eine Vernehmlassung. 