Sachverhalt: A. Der 1972 geborene X._ ist Staatsangehöriger von Bangladesch. Er reiste im April 1991 in die Schweiz ein und stellte hier ein Asylgesuch. Dieses wurde am 18. November 1993 letztinstanzlich abgewiesen. Bereits am 23. Februar 1993 hatte er die Schweizerin A._ geheiratet, worauf ihm eine Aufenthaltsbewilligung erteilt wurde. Nach Scheidung dieser Ehe wurde seine Aufenthaltsbewilligung nicht verlängert, und es wurde X._ Frist bis zum 15. April 1998 angesetzt, um die Schweiz zu verlassen. Am 17. April 1998 - zwei Tage nach Ablauf der Ausreisefrist - heiratete er erneut eine Schweizer Staatsangehörige. Aufgrund dieser neuerlichen Ehe mit der 19 Jahre älteren Y._ wurde ihm erneut eine Aufenthaltsbewilligung ausgestellt und jährlich verlängert. Am 22. April 2003 erhielt er die Niederlassungsbewilligung. Ein halbes Jahr später, mit Urteil des Bezirksgerichts Zürich vom 28. Oktober 2003, wurde auch diese Ehe geschieden. Am 3. November 2004 stellte X._ ein Gesuch um Nachzug seiner neuen Ehefrau Z._, welche er am 5. Januar 2004 in Bangladesch geheiratet haben will, sowie zweier gemeinsamer Kinder (geb. 2000 und 2002). Mit Verfügung vom 29. September 2005 wies das Migrationsamt des Kantons Zürich das Gesuch um Familiennachzug vollumfänglich ab und entzog X._ zudem die Niederlassungsbewilligung. Zur Begründung wurde u.a. vorgebracht, X._ habe den schweizerischen Behörden wissentlich verschwiegen, dass er während seiner Ehe mit Y._ eine aussereheliche bzw. gar bigame Beziehung zu einer Landsfrau geführt und mit dieser zwei aussereheliche Kinder gezeugt habe. B. Gegen die Verfügung vom 29. September 2005 rekurrierte X._ erfolglos beim Regierungsrat des Kantons Zürich. Eine von ihm erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich mit Urteil vom 3. Dezember 2008 ab. C. Mit Eingabe vom 2. Februar 2009 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Er beantragt darin im Wesentlichen, es sei ihm in Aufhebung des angefochtenen Entscheids die Niederlassungsbewilligung zu belassen. Eventualiter sei ihm eine Aufenthaltsbewilligung zu erteilen. Subeventualiter sei die Sache zur Neubeurteilung an die Vorinstanzen zurückzuweisen. Mit Verfügung vom 6. Februar 2009 erkannte der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zu.