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.

Erwägungen:
1. 1.1 Nach <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; in Kraft gewesen bis 31. Dezember 2007), das hier unbestrittenermassen noch anwendbar ist (vgl. Art. 126 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer, AuG; SR 142.20), entscheiden die zuständigen Behörden, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Es besteht damit grundsätzlich kein Anspruch auf Erteilung einer entsprechenden Bewilligung, es sei denn, der Ausländer oder seine in der Schweiz lebenden Angehörigen könnten sich auf eine Sondernorm des Bundesrechts (einschliesslich Bundesverfassungsrecht) oder eines Staatsvertrages berufen (vgl. <ref-ruling> E. 2.3 S. 189; <ref-ruling> E. 2.1 S. 284; <ref-ruling> E. 1.1.1 S. 148, mit Hinweisen).
1.2 Gegen Entscheide über den Widerruf oder die Feststellung des Erlöschens einer Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig, weil grundsätzlich ein Anspruch auf das Fortbestehen dieser Bewilligung gegeben ist (Urteil 2C_306/2008 vom 12. November 2008, mit Hinweisen). Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde kann daher grundsätzlich eingetreten werden (vgl. jedoch E. 1.3 hiernach).
1.3 Nicht zulässig ist das erhobene Rechtsmittel dagegen insoweit, als der Beschwerdeführer eventualiter - für den Fall, dass der Widerruf der Niederlassungsbewilligung geschützt wird - beantragt, es sei ihm eine Aufenthaltsbewilligung zu erteilen. Diesbezüglich fehlt es an einem Rechtsanspruch auf Bewilligungserteilung. Entgegen der vom Beschwerdeführer vorgebrachten Auffassung kann ein solcher Anspruch auch nicht aus dem verfassungsmässigen Anspruch auf Schutz des Privatlebens (Art. 8 EMRK bzw. <ref-law>) abgeleitet werden: Wie die Vorinstanz zutreffend erkannt hat und auch der Beschwerdeführer einräumt, wären hierfür besonders intensive, über eine normale Integration hinausgehende private Bindungen gesellschaftlicher oder beruflicher Natur bzw. entsprechende vertiefte soziale Beziehungen zum ausserfamiliären bzw. ausserhäuslichen Bereich erforderlich (BGE <ref-ruling> E. 3.2.1, mit Hinweisen). An solchen mangelt es im vorliegenden Fall. Die Berufung auf nicht näher substantiierte Freundschaften zu Schweizer Staatsangehörigen ist ebenso unzureichend wie die Berufstätigkeit des Beschwerdeführers, seine verhältnismässig lange Aufenthaltsdauer in der Schweiz und das angeführte Wohlverhalten während dieser Zeit. All diese Umstände sind Teil einer jeden normalen gesellschaftlichen Integration und begründen noch keinen aus dem genannten Grundrecht hergeleiteten Bewilligungsanspruch. Im Umfang des Eventualantrags kann daher auf die eingereichte Beschwerde nicht eingetreten werden.
2. Am 1. Januar 2008 ist das AuG in Kraft getreten. Massgebend für die materielle Beurteilung bleibt vorliegend aber, in analoger Anwendung von Art. 126 Abs. 1 AuG, grundsätzlich das bisherige Recht (Urteil 2C_316/2008 vom 28. November 2008 E. 1.2, mit Hinweisen).
Nach Art. 9 Abs. 4 lit. a ANAG kann die Niederlassungsbewilligung widerrufen werden, wenn der Ausländer sie durch falsche Angaben oder wissentliches Verschweigen wesentlicher Tatsachen erschlichen hat.
Art. 3 Abs. 2 ANAG verpflichtet den Ausländer, der Behörde wahrheitsgetreu über alles Auskunft zu geben, was für den Bewilligungsentscheid massgebend sein kann.
3. 3.1 Im vorliegenden Fall ist unbestritten, dass der Beschwerdeführer die zürcherischen Behörden über seine aussereheliche Beziehung in seinem Heimatstaat und insbesondere die daraus hervorgegangenen Kinder nicht informiert hat. Er macht jedoch geltend, ein Erschleichen i.S. von Art. 9 Abs. 4 lit. a ANAG setze voraus, dass Tatsachen verschwiegen würden, nach denen explizit gefragt worden sei. Im vorliegenden Fall ergebe sich eine solche behördliche Fragepflicht aus dem Grundsatz von Treu und Glauben: Wenn das Vorhandensein von unehelichen Kindern für die Frage der Bewilligungserteilung derart wesentlich sei, müsse vom Migrationsamt erwartet werden, diese Frage auf den entsprechenden Formularen zu stellen. Der Beschwerdeführer habe die Wesentlichkeit dieses Umstands jedenfalls nicht erkannt und habe keine Täuschungsabsicht gehabt. Die gegenteilige Schlussfolgerung der Vorinstanz laufe auf eine offensichtlich unrichtige Feststellung des Sachverhaltes hinaus.
3.2 Es kann offen bleiben, inwieweit die erhobene Rüge tatsächlich die Feststellung des Sachverhaltes und nicht vielmehr dessen Würdigung (und mithin eine Rechtsfrage) berührt. Die Einwendungen des Beschwerdeführers vermögen jedenfalls nicht zu überzeugen: Wie die Vorinstanz zutreffend ausgeführt hat, sind gemäss der ständigen bundesgerichtlichen Rechtsprechung nicht nur jene Umstände wesentlich, nach denen die Fremdenpolizei ausdrücklich fragt, sondern auch solche, von denen der Gesuchsteller wissen muss, dass sie für den Bewilligungsentscheid massgeblich sind. Entgegen der Ansicht des Beschwerdeführers ist es derart offensichtlich, dass das Vorhandensein einer ausserehelichen Beziehung und von ausserehelichen Kindern im Heimatstaat in fremdenpolizeilicher Hinsicht von Relevanz ist, dass dies selbst einer gänzlich rechtsunkundigen Person ohne weiteres klar sein muss (vgl. Urteil 2A.423/2006 vom 26. Oktober 2006 E. 2.1; 2A.551/2003 vom 21. November 2003 E. 2.1 f., mit Hinweisen). Der Beschwerdeführer kann daher das Bestehen einer Täuschungsabsicht nicht mit Erfolg bestreiten.
Bei dieser Sachlage ist es nicht zu beanstanden, wenn die Vorinstanz zum Schluss gekommen ist, dass der Beschwerdeführer dem Migrationsamt wesentliche Tatsachen wissentlich verschwiegen und sich seine Niederlassungsbewilligung auf diese Weise erschlichen hat.
4. 4.1 Der Beschwerdeführer bestreitet sodann die Verhältnismässigkeit des Entzugs der Niederlassungsbewilligung und rügt, dass den Vorinstanzen bei dieser Prüfung qualifizierte Ermessensfehler unterlaufen seien, welche als Rechtsverletzungen i.S. von <ref-law> bezeichnet werden müssten. Er verweist in diesem Zusammenhang im Wesentlichen darauf, dass er nunmehr schon seit 18 Jahren in der Schweiz lebe, in dieser Zeit noch nie Anlass zu Klagen gegeben habe und hier beruflich und sozial voll integriert sei. Ebenso sei im Rahmen der Verhältnismässigkeitsprüfung zu berücksichtigen, dass seit Inkrafttreten des AuG ein Widerruf der Niederlassungsbewilligung wegen Verschweigens wesentlicher Tatsachen nicht mehr möglich sei, sofern sich der Betroffene mehr als 15 Jahre ununterbrochen und ordnungsgemäss in der Schweiz aufgehalten habe.
4.2 Soweit der Beschwerdeführer die behauptete Unverhältnismässigkeit des angefochtenen Entscheids mit seinem lange andauernden Aufenthalt und seiner fortgeschrittenen Integration in der Schweiz begründet, kann seiner Argumentation nicht gefolgt werden: Wie bereits das Verwaltungsgericht zu Recht erkannt hat, verbrachte er seine gesamte Kindheit und die prägenden Jugendjahre in seinem Heimatland und ist mit der dortigen Sprache und den örtlichen Verhältnissen vertraut. Während der Ehe mit einer Schweizerin hat er in Bangladesch eine aussereheliche Beziehung geführt und eine Familie gegründet, mit welcher er jetzt offenbar auch zusammenleben will. Unter diesem Aspekt erscheint seine Rückkehr in das gemeinsame Heimatland naheliegend und zumutbar. Ob die in casu noch nicht anwendbaren Bestimmungen des AuG allenfalls eine für den Beschwerdeführer vorteilhaftere Regelung vorgesehen hätten, ist nicht entscheidend, zumal dieser Umstand bei der vorliegenden Sachlage ohnehin nicht hinreichend bedeutsam erscheint, um die Verhältnismässigkeit des Widerrufs der Niederlassungsbewilligung in Frage zu stellen.
5. Aus den genannten Gründen ergibt sich, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten offensichtlich unbegründet und daher im vereinfachten Verfahren gemäss <ref-law> abzuweisen ist, soweit darauf überhaupt eingetreten werden kann.
Da die Beschwerde von vornherein aussichtslos erschien, kann dem Gesuch um unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren nicht entsprochen werden (<ref-law>). Somit sind die Gerichtskosten (<ref-law>) dem Beschwerdeführer aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, der Sicherheitsdirektion, dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich (4. Kammer) sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 5. März 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Zähndler