Sachverhalt:
A. A.X._ (geb. 1976) ist Staatsangehöriger von Bangladesch und reiste am 23. April 2002 als Asylbewerber erstmals in die Schweiz ein. Am 3. September 2002 heiratete er die Schweizer Bürgerin B.X._ (geb. 1982), welche Mutter des aus einer früheren Beziehung hervorgegangen Sohnes C.X._ (geb. 2001) ist. Aufgrund der Heirat erhielt A.X._ eine Aufenthaltsbewilligung für den Kanton Zürich. Am 12. November 2002 brachte B.X._ ihre Tochter D.X._ - ebenfalls aus einer früheren Beziehung hervorgegangen - zur Welt. Am 3. Oktober 2003 wurde das Asylverfahren als durch Rückzug erledigt abgeschrieben. Am 12. Oktober 2005 ging aus der Beziehung von B.X._ mit E._ die Tochter F.X._ hervor.
Am 5. Januar 2006 teilte die Sicherheitsdirektion des Kantons Zürich A.X._ mit, sie beabsichtige, ihm den weiteren Aufenthalt im Kanton Zürich zu verweigern, weil er sich rechtsmissbräuchlich auf seine Ehe berufe. Zuvor hatten polizeiliche Ermittlungen den Verdacht einer Scheinehe ergeben. Nachdem sich A.X._ erneut an der Wohnadresse seiner Ehefrau angemeldet hatte und diese schriftlich bestätigte, sie sei zur Wiederaufnahme der Ehegemeinschaft bereit, verlängerte die Sicherheitsdirektion die Aufenthaltsbewilligung und erteilte am 13. November 2007 die Niederlassungsbewilligung für den Kanton Zürich. Mit Verfügung vom 3. Juni 2008 stellte das Bezirksgericht Winterthur fest, dass die Eheleute X._ seit dem 14. Mai 2008 getrennt lebten.
B. Nachdem B.X._ erneut bestätigt hatte, eine Scheinehe eingegangen zu sein, widerrief die Sicherheitsdirektion mit Verfügung vom 21. Januar 2009 die Niederlassungsbewilligung von A.X._ und setzte ihm Frist zum Verlassen der Schweiz bis zum 31. März 2009. Dagegen gelangte A.X._ mit Rekurs an den Regierungsrat des Kantons Zürich, der das Rechtsmittel am 15. Juni 2011 abwies. Das hiegegen angerufene Verwaltungsgericht des Kantons Zürich erkannte mit Urteil vom 26. Oktober 2011 auf Abweisung der Beschwerde und setzte die Ausreisefrist neu auf den 31. Dezember 2011 fest.
C. Mit Eingabe vom 1. Dezember 2011 erhebt A.X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt, die Verfügung der Sicherheitsdirektion vom 15. Juni 2011 (recte: 21. Januar 2009) bzw. das Urteil des Verwaltungsgerichts vom 26. Oktober 2011 seien aufzuheben und von einem Widerruf seiner Niederlassungsbewilligung sei abzusehen.
Das Verwaltungsgericht des Kantons Zürich verzichtet auf eine Vernehmlassung, während der Regierungsrat des Kantons Zürich sowie das Bundesamt für Migration die Abweisung der Beschwerde beantragen.
Mit Verfügung vom 6. Dezember 2011 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Gegen den angefochtenen kantonal letztinstanzlichen Endentscheid über den Widerruf der Niederlassungsbewilligung (Art. 63 i.V.m. Art. 62 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [AuG; SR 142.20]) ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht zulässig, weil grundsätzlich ein Anspruch auf das Fortbestehen dieser Bewilligung gegeben ist (vgl. Art. 83 lit. c Ziff. 2, Art. 86 Abs. 1 lit. d sowie Art. 90 BGG; <ref-ruling> E. 1.2.1 S. 4).
1.2 Unzulässig ist das Rechtsmittel, soweit es sich gegen einen kantonal vorinstanzlichen Entscheid richtet, da dieser durch das verwaltungsgerichtliche Urteil ersetzt worden ist und als mit angefochten gilt (sog. Devolutiveffekt; vgl. <ref-ruling> E. 1.4 S. 144; <ref-ruling> E. 1 S. 441).
1.3 Mit der Beschwerde kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). 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 Art. 95 BGG beruht (Art. 97 Abs. 1 BGG bzw. Art. 105 Abs. 2 BGG). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG; vgl. <ref-ruling> E. 1.5 S. 146 f.).
2. Streitgegenstand bildet der Widerruf der Niederlassungsbewilligung durch die Migrationsbehörden des Kantons Zürich. Die Beschwerde befasst sich mit der vorinstanzlichen Feststellung und Würdigung des Sachverhalts. In Abweichung vom angefochtenen Urteil kommt der Beschwerdeführer zum Schluss, es fehle "mangels relevanter neuer Tatsachen" an den Voraussetzungen für eine Scheinehe, was zur Folge hätte, dass der Widerrufsgrund der falschen Angaben oder des Verschweigens wesentlicher Tatsachen im Bewilligungsverfahren entfiele. Für den Fall, dass der Tatbestand der Scheinehe dennoch erfüllt wäre, bemängelt der Beschwerdeführer, der angefochtene Entscheid erweise sich insofern als unverhältnismässig, als die Vorinstanz die massgebenden Bestimmungen des AuG sowie der EMRK unrichtig angewendet und damit die Interessenabwägung unzutreffend vorgenommen habe.
3. 3.1 Zur Frage der Scheinehe ist in der Regel kein direkter Beweis möglich, sodass auf Indizien zurückgegriffen werden muss (<ref-ruling> E. 2b S. 295; <ref-ruling> E. 3b S. 101 f.). Bei Anhaltspunkten dieser Art handelt es sich um Tatfragen (<ref-ruling> E. 2.3 mit Hinweisen), weshalb das Bundesgericht grundsätzlich an die vorinstanzlichen Feststellungen gebunden ist (Art. 105 Abs. 1 BGG). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) zum Schluss führen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung ausländerrechtlicher Vorschriften (<ref-ruling> E. 2.3 S. 152; Urteil 2C_244/2010 vom 15. November 2010 E. 2.3).
3.2 Der Beschwerdeführer macht geltend, ein Widerruf sei ausgeschlossen, wenn die Behörde trotz hinreichender Kenntnisse der massgebenden Umstände die Niederlassungsbewilligung erteilt habe. Entgegen der Auffassung der Vorinstanz lägen keine neuen Tatsachen vor. Weiter sei auch der fehlende Wille der Ehefrau zur Wiederaufnahme der Ehe aktenmässig nicht belegt.
Diese Argumentation zielt ins Leere: Wie die Vorinstanz ausführlich dargelegt hat (vgl. angefochtener Entscheid E. 4.2) lässt der Umstand, dass der Verdacht einer Scheinehe bereits früher einmal im Raum stand, den nun angefochtenen Widerruf der Niederlassungsbewilligung keineswegs als unzulässig erscheinen. Gemäss den verbindlichen Feststellungen der Vorinstanz hat die Ehefrau des Beschwerdeführers zwar bereits im September 2005 ausgesagt, sie führe mit dem Beschwerdeführer eine Scheinehe und dieser habe ihr für die Eheschliessung einen Betrag von Fr. 20'000.-- zukommen lassen. Nachdem die Ehefrau schriftlich erklärt hatte, sie wolle wieder mit ihrem Ehemann zusammenleben und dieser sich wieder an der Wohnadresse der Ehefrau angemeldet hatte, verfügte das Migrationsamt jedoch die Verlängerung der Aufenthaltsbewilligung bzw. die Erteilung der Niederlassungsbewilligung. Am 30. Oktober 2008 bestätigte aber die Ehefrau erneut, mit A.X._ eine Scheinehe eingegangen zu sein; sie habe vom Frühling 2004 bis Mitte Oktober 2008 mit dem Vater ihrer Tochter F.X._ zusammengelebt. Zudem sei sie bedroht worden, um die schriftlichen Erklärungen, wonach sie das Eheleben wieder aufnehmen wolle, zu unterzeichnen. Daraus erhellt ohne Weiteres, dass die Migrationsbehörde nach der Erteilung der Niederlassungsbewilligung am 13. November 2007 von neuen Tatsachen Kenntnis erhielt, die eine Neubeurteilung möglich machten (vgl. Urteil 2C_911/2011 vom 3. Mai 2012 E. 3.4).
Weiter sind die Feststellungen der Vorinstanz betreffend die Dauer der Beziehung bzw. dem Willen der Ehefrau zur Wiederaufnahme der ehelichen Gemeinschaft nicht offensichtlich unrichtig: Die Aussagen der Ehefrau in den polizeilichen Befragungen in den Jahren 2005 und 2008 sprechen klar dafür, dass gar nie ein Ehewille bestand. Die angeblich von der Ehefrau verfassten Schreiben vermögen daran nichts zu ändern. Zu den vorgenommenen formellen Anmeldungen des Beschwerdeführers am Wohnsitz der Ehefrau (2006 sowie erneut im September 2011) kam es offensichtlich unter dem Druck des drohenden Widerrufs der Aufenthaltsbewilligung bzw. des vorliegenden Beschwerdeverfahrens. Die Vorinstanz hat weiter festgestellt, die Aussagen des ehemaligen Partners und Vaters der gemeinsamen Tochter stimmten mit den Aussagen B.X._s überein, wonach diese bis Mitte Oktober 2008 zusammen lebten.
3.3 Sodann hat die Vorinstanz weitere Indizien für das Vorliegen einer Scheinehe festgestellt (vgl. angefochtener Entscheid E. 4.3.2): Ohne Heirat hätte der Beschwerdeführer keine Aussicht auf eine Aufenthaltsbewilligung gehabt. Der Heirat ging eine sehr kurze Bekanntschaft voraus und die Ehefrau stand im Zeitpunkt der Heirat kurz vor der Geburt ihrer zweiten Tochter, deren Vater nicht der Beschwerdeführer ist. Sodann unterhielt B.X._ während der Ehe eine viereinhalb Jahre dauernde Beziehung mit einem anderen Mann, woraus die dritte Tochter hervorging. Für eine Scheinehe spricht schliesslich auch der Umstand, dass die Ehefrau - psychisch und finanziell wenig stabil - erfahrungsgemäss der typischen Zielgruppe entspricht, die von Ausländern für die Eingehung von Scheinehen gesucht wird (vgl. <ref-ruling> E. 2c S. 296).
3.4 An der Art der Erhebung und Würdigung der massgebenden Tatsachen ist damit verfassungsrechtlich nichts auszusetzen. Mit freier Kognition zu prüfen bleibt der Schluss der Vorinstanz, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung ausländerrechtlicher Vorschriften (vgl. E. 3.1 hiervor). Vor dem Hintergrund der gewonnenen Indizien ist diese Schlussfolgerung ohne Weiteres nachvollziehbar und erscheint als durchaus sachrichtig. Sie drängt sich geradezu auf und ist damit keinesfalls bundesrechtswidrig.
4. 4.1 Nach Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. a AuG, die einen Eingriffsgrund im Sinne von Art. 8 Ziff. 2 EMRK darstellen, kann eine Niederlassungsbewilligung widerrufen werden, soweit die ausländische Person im Bewilligungsverfahren falsche Angaben gemacht oder wesentliche Tatsachen verschwiegen hat. Die zum Widerruf früheren Rechts (Art. 9 Abs. 2 lit. a und Abs. 4 lit. a des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer [ANAG; BS 1 121]) entwickelte Rechtsprechung gilt sinngemäss weiter (Urteil 2C_136/2012 vom 17. April 2012 E. 3.1).
4.2 Der Beschwerdeführer stellt sich sinngemäss auf den Standpunkt, er sei in seinem Vertrauen auf den Bestand der erteilten Niederlassungsbewilligung zu schützen. Es mag zutreffen, dass die Migrationsbehörden schon vor der Erteilung der Niederlassungsbewilligung den Verdacht auf Scheinehe äusserten und ihm diese trotzdem erteilten. Soweit der Beschwerdeführer aber vorbringt, die Sachlage habe sich seither nicht verändert, ist dies - wie bereits in E. 3.2 hiervor erwähnt - unzutreffend: Die polizeilichen Erhebungen, auf die sich die Vorinstanz im Wesentlichen stützt, erfolgten erst im Anschluss an die Erteilung der Niederlassungsbewilligung und mussten zwangsläufig zu einer Neubeurteilung durch die Migrationsbehörden führen. Grundbedingung des Gebots von Treu und Glauben gemäss Art. 9 BV ist denn auch, dass die Darstellung des Sachverhalts durch die um Auskunft oder Bewilligung nachsuchende Person überhaupt "vollständig und richtig" erfolgt (Urteil 2C_911/2011 vom 3. Mai 2012 E. 4.2 mit Hinweisen). Daran fehlte es hier gerade, sodass die Rüge von vornherein nicht stichhaltig ist.
4.3 Hätte demnach die Ausländerbehörde davon Kenntnis gehabt, dass ein eheliches Zusammenleben gar nie bestanden hatte und auch nicht beabsichtigt wurde, wäre dem Beschwerdeführer weder die Aufenthaltsbewilligung noch die Niederlassungsbewilligung erteilt worden. Damit besteht offensichtlich ein Widerrufsgrund im Sinne von Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. a AuG (Urteil 2C_656/2011 vom 8. Mai 2012 E. 2.2).
4.4 Der Widerruf der Niederlassungsbewilligung ist somit nicht zu beanstanden, soweit nicht die Verhältnismässigkeitsprüfung zu einem andern Schluss führt.
4.4.1 Mit Recht verwirft die Vorinstanz die Anwendbarkeit von Art. 8 Ziff. 1 EMRK unter dem Aspekt des Schutzes des Familienlebens, kann diese Norm doch bloss angerufen werden, soweit eine staatliche Entfernungs- oder Fernhaltemassnahme überhaupt zur Trennung von "Familienmitgliedern" führt (<ref-ruling> E. 2.1 S. 155; <ref-ruling> E. 3a S. 342). Handelt es sich um eine Scheinehe, mangelt es an einer (Kern-)Familie im eigentlichen Sinn und kann Art. 8 Ziff. 1 EMRK unter dem Aspekt des Schutzes des Familienlebens nicht angerufen werden.
4.4.2 Nichts anderes ergibt sich unter dem Gesichtspunkt des Schutzes des Privatlebens. Aus einer rein faktischen Anwesenheit kann im Lichte von Art. 8 Ziff. 1 EMRK grundsätzlich kein Aufenthaltsrecht abgeleitet werden (vgl. Urteil 2C_730/2011 vom 24. Februar 2012 E. 4.2). Zu verlangen wäre eine besonders intensive, über eine normale Integration hinausgehende private Bindung gesellschaftlicher oder beruflicher Natur bzw. entsprechend vertiefte soziale Beziehung zum ausserfamiliären oder ausserhäuslichen Bereich (<ref-ruling> E. 3.2.1 S. 286), was hier nicht ersichtlich ist. Die finanzielle Unabhängigkeit ebenso wie die strafrechtliche Unbescholtenheit sind zwar durchaus zu Gunsten des Beschwerdeführers zu werten, vermögen aber letztlich das öffentliche Interesse an der Fernhaltung einer ausländischen Person, welche die Migrationsbehörde bewusst in einen Grundlagenirrtum versetzte, um auf diese Weise zunächst eine Aufenthalts- und später eine Niederlassungsbewilligung zu erlangen, nicht aufzuwiegen.
4.4.3 Die vorinstanzliche Rechtsgüterabwägung ist mithin nicht zu beanstanden und verletzt weder Völker- noch Landesrecht. Das angefochtene Urteil ist insofern zu bestätigen und die Beschwerde abzuweisen, soweit darauf einzutreten ist.
5. Diesem Ausgang entsprechend hat der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65 f. BGG). Das Gesuch um unentgeltliche Prozessführung und Verbeiständung ist nach Art. 64 BGG wegen Aussichtslosigkeit abzuweisen. Parteientschädigungen werden nicht zugesprochen (vgl. Art. 68 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Prozessführung und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 11. Juli 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger