Sachverhalt:
A. Der chinesische Staatsangehörige X._ (geb. 1978) reiste am 23. August 1998 in die Schweiz ein und erhielt eine Aufenthaltsbewilligung als Hotelfachschüler für den Kanton Luzern, die letztmals bis zum 31. August 2002 verlängert wurde. Am 28. Oktober 2002 heiratete er eine 23 Jahre ältere Schweizer Bürgerin. Nach seiner Anmeldung in Y._/ZH, dem Wohnort seiner Ehefrau, wurde ihm die Aufenthaltsbewilligung zum Verbleib bei seiner Ehegattin (letztmals verlängert bis zum 27. Oktober 2007) erteilt.
B. Am 30. August 2007 ersuchte X._ um Verlängerung der Aufenthaltsbewilligung bzw. um Erteilung der Niederlassungsbewilligung. Mit Verfügung vom 7. Januar 2008 wies das Migrationsamt des Kantons Zürich das Gesuch ab mit der Begründung, X._ habe sich in rechtsmissbräuchlicher Art auf die seit Jahren nur noch formell bestehende Ehe berufen und sich auf diese Weise die Verlängerung der Bewilligung erschlichen, weshalb ein Widerrufsgrund bestehe.
Den dagegen erhobenen Rekurs wies der Regierungsrat mit Beschluss vom 17. Dezember 2008 ab mit der Begründung, es handle sich um eine Scheinehe. Gegen den Regierungsratsbeschluss beschwerte sich X._ ohne Erfolg beim Verwaltungsgericht des Kantons Zürich, das ebenfalls vom Vorliegen einer Scheinehe ausgeht.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 29. Oktober 2009 beantragt X._, den Entscheid des Verwaltungsgerichts des Kantons Zürich vom 26. August 2009 aufzuheben und dem Beschwerdeführer die Niederlassungsbewilligung zu erteilen, eventualiter die Aufenthaltsbewilligung zu verlängern.
D. Die Staatskanzlei des Kantons Zürich, im Auftrag des Regierungsrates, sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten ist.

Erwägungen:
1. 1.1 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; BS 1 121) und seinen Ausführungserlassen (Art. 126 Abs. 1 AuG).
1.2 Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen ausgeschlossen, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht. Als ausländischer Ehegatte einer Schweizer Bürgerin hat der Beschwerdeführer nach dem hier noch massgebenden Art. 7 ANAG (in der Fassung vom 23. März 1990, AS 1991 1034 1043) grundsätzlich einen Anspruch auf Erteilung einer Aufenthaltsbewilligung. Ob ein Grund besteht, die Bewilligung dennoch zu verweigern, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (vgl. <ref-ruling> E. 1b S. 266; <ref-ruling> E. 1.1.2 S. 148 f.) Auf die frist- und formgerecht eingereichte Beschwerde ist somit grundsätzlich einzutreten.
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (vgl. <ref-ruling> E. 1.4 S. 400). Hinsichtlich der Verletzung von Grundrechten gilt indessen eine qualifizierte Rügepflicht (<ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254). Soweit vorliegend eine diesen Anforderungen genügende Begründung fehlt, kann auf die Beschwerde nicht eingetreten werden. Im Übrigen findet Art. 6 EMRK auf fremdenpolizeirechtliche Streitigkeiten ohnehin keine Anwendung (Urteil des Europäischen Gerichtshofs für Menschenrechte vom 7. April 1994, in: VPB 1994 58.99 S. 719; vgl. <ref-ruling>).
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Sachverhaltsfeststellung kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig erfolgt 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 (<ref-law>), setzt zudem voraus, dass die Behebung des Mangels sich für den Ausgang des Verfahrens als entscheidend erweisen 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 Erklärung der Schwägerin des Beschwerdeführers vom 24. Oktober 2009 ist als sog. "echtes" Novum unbeachtlich (<ref-ruling> E. 2.1 mit Hinweisen); sie wäre ohnehin nicht geeignet, am Ausgang des Verfahrens etwas zu ändern.
2. 2.1 Gemäss Art. 7 Abs. 2 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers keinen Anspruch auf Erteilung der ihm nach Abs. 1 grundsätzlich zustehenden Aufenthaltsbewilligung (bzw. Niederlassungsbewilligung), wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern und namentlich jene über die Begrenzung der Zahl der Ausländer zu umgehen. Erfasst wird davon die sog. Scheinehe bzw. Ausländerrechtsehe. Ein Bewilligungsanspruch entfällt demnach, wenn zum Vornherein nie der Wille bestand, eine dauerhafte Gemeinschaft zu begründen, und der einzige Zweck der Heirat darin liegt, dem Ausländer zu einer fremdenpolizeilichen Bewilligung zu verhelfen.
2.2 Ob eine Scheinehe geschlossen wurde, entzieht sich oft einem direkten Beweis und ist bloss durch Indizien zu erstellen (<ref-ruling> E. 10.2 und 10.3 S. 135 f. mit Hinweis). Feststellungen des kantonalen Richters über das Bestehen von solchen Hinweisen können äussere Gegebenheiten, aber auch innere psychische Vorgänge betreffen (Wille der Ehegatten). In beiden Fällen handelt es sich um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG; <ref-ruling> E. 1.4.3 S. 254 f.). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung fremdenpolizeilicher Vorschriften (BGE <ref-ruling> E. 2.3 S. 152 mit Hinweisen).
Für die Annahme einer Scheinehe bedarf es konkreter Hinweise darauf, dass die Ehegatten nicht eine eigentliche Lebensgemeinschaft führen wollen, sondern die Ehe nur aus fremdenpolizeilichen Überlegungen geschlossen haben. Diesbezügliche Indizien lassen sich unter anderem darin erblicken, dass dem Ausländer die Wegweisung drohte, etwa weil er ohne Heirat keine Aufenthaltsbewilligung erhalten hätte oder sie ihm nicht verlängert worden wäre. Für das Vorliegen einer Ausländerrechtsehe können sodann die Umstände und die kurze Dauer der Bekanntschaft sprechen sowie insbesondere die Tatsache, dass die Ehegatten eine Wohngemeinschaft gar nie aufgenommen haben. Dasselbe gilt, wenn für die Heirat eine Bezahlung vereinbart wurde oder wenn ein erheblicher Altersunterschied zwischen den Ehepartnern besteht. Dass die Begründung einer wirklichen Lebensgemeinschaft gewollt war, kann umgekehrt nicht schon daraus abgeleitet werden, dass die Ehegatten während einer gewissen Zeit zusammenlebten und intime Beziehungen unterhielten; ein derartiges Verhalten kann auch nur vorgespiegelt sein, um die Behörden zu täuschen (<ref-ruling> E. 2b S. 295 mit Hinweisen). Eine Scheinehe liegt demgegenüber nicht bereits dann vor, wenn ausländerrechtliche Motive für den Eheschluss mitentscheidend waren. Erforderlich ist zusätzlich, dass der Wille zur Führung einer Lebensgemeinschaft - zumindest bei einem der Ehepartner - von Anfang an nicht gegeben ist (vgl. <ref-ruling> E. 3b S. 101 f. mit Hinweisen).
2.3 Gemäss den für das Bundesgericht verbindlichen Feststellungen (E. 1.4) der Vorinstanz ist der Beschwerdeführer eine Scheinehe eingegangen. Das Verwaltungsgericht konnte sich dafür auf zahlreiche Indizien stützen: Ohne Heirat wäre dem Beschwerdeführer keine Aufenthaltsbewilligung mehr erteilt worden. Die Ehegatten haben sich durch eine Drittperson, die der Polizei als Vermittlerin von Scheinehen bekannt ist, kennen gelernt. Nichts deutet darauf hin, dass sich diese vermittelte Begegnung in der Folge zu einer Liebesbeziehung entwickelt hat, wie in der Beschwerdeschrift geltend gemacht wird. Auch die angebliche Dauer der Bekanntschaft vor der Heirat ist in keiner Weise nachgewiesen. Weiter fällt auf, dass die Ehegattin, die zudem 23 Jahre älter ist als der Beschwerdeführer, die Heirat vor ihrer Familie verheimlicht hat. Sogar ihre Schwester und der Schwager, die im gleichen Haus wohnen wie sie, hatten keine Kenntnis von der vor mehreren Jahren mit dem Beschwerdeführer eingegangenen Ehe. Weiter haben weder die Schwester, noch deren Ehemann, noch andere Bewohner des Miethauses den Beschwerdeführer dort je angetroffen, obwohl er angeblich seit der Heirat im Jahre 2002 mit der Ehegattin zusammen wohnt. Auch aufgrund der Feststellungen anlässlich des in der Wohnung vorgenommenen Augenscheins lässt sich nicht auf das Bestehen einer ehelichen Gemeinschaft schliessen. Selbst wenn der Beschwerdeführer dort ab und zu die Nacht verbringen sollte und etwas saubere Kleider sowie eine Zahnbürste deponiert hat, vermag dies die eindeutigen Hinweise auf eine Ausländerrechtsehe nicht zu widerlegen. Im Übrigen hat der Beschwerdeführer auch nicht nachgewiesen, dass er sich ernsthaft darum bemüht hätte, in der Nähe von Y._ eine Anstellung zu finden bzw. Arbeit und Wohnort so zu organisieren, dass ein eheliches Zusammenleben möglich gewesen wäre.
Anhaltspunkte dafür, dass die Feststellungen des Verwaltungsgerichts des Kantons Zürich zum Sachverhalt offensichtlich unrichtig wären, sind nicht ersichtlich und gehen namentlich auch nicht aus den Vorbringen des Beschwerdeführers hervor. Zwar müssen die Behörden den Sachverhalt grundsätzlich von Amtes wegen untersuchen. Der Untersuchungsgrundsatz wird aber durch die Mitwirkungspflicht der Parteien relativiert. Diese kommt naturgemäss gerade für solche Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vernünftigem Aufwand erhoben werden können (vgl. <ref-ruling> E. 2b S. 365; Urteil 2A.715/2005 vom 13. Februar 2006 E. 2.4 und 2.7.1). Dies gilt umso mehr, wenn gewichtige Anzeichen für eine Ausländerrechtsehe sprechen; dann kann von den Eheleuten erwartet werden, dass sie von sich aus Umstände, die auf den echten Ehewillen hindeuten, vorbringen und diese belegen. Es genügt nicht, in appellatorischer Weise bloss die eigene Sicht der Dinge vorzutragen.
2.4 Bei gesamthafter Betrachtung aller Indizien durfte die Vorinstanz ohne Weiteres auf eine Scheinehe schliessen. Was der Beschwerdeführer dagegen einwendet, vermag diese Würdigung nicht zu erschüttern. Das Urteil 2C_435/2007 vom 10. März 2008, auf das er sich mehrfach beruft, betrifft einen mit vorliegender Angelegenheit nicht vergleichbaren Sachverhalt (in jenem Fall hielt sich der ausländische Ehegatte noch nicht in der Schweiz auf und hatte daher gar keine Gelegenheit zum ehelichen Zusammenleben), weshalb der Beschwerdeführer daraus nichts zu seinen Gunsten ableiten kann. Abgesehen davon, dass die gerügte Verletzung von <ref-law> wohl kaum genügend begründet ist, könnte von einer Diskriminierung wegen der gewählten Lebensform ohnehin nicht die Rede sein. Weder wird die Heirat zwischen Partnern mit grossem Altersunterschied "staatlich sanktioniert", noch steht das Ausländerrecht bei Vorliegen wichtiger Gründe getrennten Wohnorten der Ehegatten entgegen, indessen ist auch dann erforderlich, dass eine echte eheliche Gemeinschaft besteht, was hier offensichtlich nicht der Fall ist.
2.5 Damit verstösst der angefochtene Entscheid nicht gegen Bundesrecht. Im Fall einer Scheinehe betrifft die Verweigerung der Aufenthaltsbewilligung bzw. der Niederlassungsbewilligung das nach Art. 8 EMRK und <ref-law> geschützte Familienleben zum Vornherein nicht. Weitere Ausführungen dazu erübrigen sich. Es genügt, ergänzend auf die Erwägungen im angefochtenen Entscheid zu verweisen.
3. Besteht kein Anwesenheitsanspruch nach Art. 7 ANAG, bedarf es keiner Prüfung, ob dem Beschwerdeführer die Rückreise ins Heimatland zumutbar ist. Auf seine Darlegungen betreffend Integration und Verhalten in der Schweiz sowie angebliche mit der Rückkehr ins Heimatland verbundene Schwierigkeiten ist daher nicht einzugehen. Diese könnten allenfalls bei der Prüfung der Erteilung einer Aufenthaltsbewilligung gestützt auf Art. 4 ANAG, der eine Bewilligung ins freie Ermessen der Behörden stellt, berücksichtigt werden. Diesbezüglich ist jedoch die Beschwerde ans Bundesgericht ausgeschlossen.
4. 4.1 Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
4.2 Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig (Art. 65 f. BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Sicherheitsdirektion des Kantons Zürich, dem Regierungsrat des Kantons Zürich, dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 15. April 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Zünd Dubs