Sachverhalt:
A. X._ (geb. 1965), Staatsangehöriger von Sri Lanka, reiste am 14. August 1996 in die Schweiz ein und stellte ein Asylgesuch. Dieses wurde am 7. März 1997 abgewiesen. Auf die dagegen erhobene Beschwerde trat die Asylrekurskommission nicht ein. Wegen fehlender Reisedokumente konnte die Wegweisung von X._ jedoch nicht vollzogen werden.
Am 7. Juli 1998 heiratete X._ die aus der Republik Elfenbeinküste stammende Schweizerin Y._, welche bereits zwei Kinder hatte. Am 3. Februar 2000 wies das Bezirksgericht Bülach die auf eine unheilbare Zerrüttung der Ehe gemäss alt <ref-law> gestützte Scheidungsklage der Ehefrau ab. Am 5. Juni 2000 erteilte das Migrationsamt des Kantons Zürich X._ eine Aufenthaltsbewilligung zum Verbleib bei der Ehefrau, die es in der Folge bis zum 6. Januar 2003 verlängerte. Am 12. Februar 2004 wurde die Ehe vom Bezirksgericht Zürich rechtskräftig geschieden.
Zwischen 2001 und 2003 wurde X._ in vier Strafverfahren unter anderem wegen mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz, Widerhandlung gegen die Ausländergesetzgebung, grober Verkehrsregelverletzung, Hehlerei und versuchten Diebstahls zu insgesamt 205 Tagen Gefängnis und einer Busse von Fr. 4'000.-- verurteilt.
B. Mit Verfügung vom 5. April 2006 wies das Migrationsamt die Gesuche von X._ vom 19. Dezember 2002 und vom 23. Dezember 2003 um Verlängerung der Aufenthaltsbewilligung bzw. um Erteilung einer Niederlassungsbewilligung ab. Es erwog im Wesentlichen, X._ berufe sich rechtsmissbräuchlich auf eine nur noch formell bestehende Ehe und habe daher keinen Anspruch auf Erteilung der Niederlassungsbewilligung bzw. Verlängerung der Aufenthaltsbewilligung. Aufgrund der nicht sehr starken Verwurzelung des Betroffenen in der Schweiz und seiner Straffälligkeit rechtfertige sich auch gestützt auf Art. 4 ANAG kein weiterer Aufenthalt.
Dagegen rekurrierte X._ an den Regierungsrat des Kantons Zürich. Am 3. Februar 2009 stellte X._ ein Gesuch um Erteilung einer Härtefallbewilligung gestützt auf das neue Ausländergesetz. Mit Beschluss vom 31. März 2009 wies der Regierungsrat den Rekurs ab. X._ beschwerte sich gegen den Regierungsratsbeschluss ohne Erfolg beim Verwaltungsgericht des Kantons Zürich.
C. Mit Beschwerde an das Bundesgericht vom 21. Januar 2010 beantragt X._, den Entscheid des Verwaltungsgerichts des Kantons Zürich vom 21. Oktober 2009 aufzuheben und ihm die Niederlassungsbewilligung zu erteilen, eventualiter die Aufenthaltsbewilligung zu verlängern. Subeventualiter ersucht er um Rückweisung der Sache an die Vorinstanz zur Neubeurteilung. Weiter beantragt er, es sei festzustellen, dass das Verfahren betreffend Verlängerung der Aufenthaltsbewilligung bis zur Erteilung der Niederlassungsbewilligung nicht innert der verfassungsrechtlich gebotenen Frist abgeschlossen wurde. Im Übrigen stellt er das Begehren, der Beschwerde die aufschiebende Wirkung zuzuerkennen.
Die Staatskanzlei - im Auftrag des Regierungsrates - und das Verwaltungsgericht des Kantons Zürich sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
D. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat mit Verfügung vom 26. Januar 2010 der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 <ref-law> schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
1.2 Das streitige Gesuch um Verlängerung der Aufenthaltsbewilligung bzw. Erteilung der Niederlassungsbewilligung 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.3 Nach Art. 7 Abs. 1 ANAG (in der Fassung vom 23. März 1990) hat der ausländische Ehegatte eines Schweizer Bürgers grundsätzlich Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung und nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren auf die Niederlassungsbewilligung (Satz 1).
Der Beschwerdeführer war vom 7. Juli 1998 bis zum 12. Februar 2004 und damit mehr als fünf Jahre mit einer Schweizer Bürgerin verheiratet. Die Frage, ob die Bewilligung verweigert werden durfte, weil einer der in Art. 7 ANAG vorgesehenen Ausnahmetatbestände oder ein Verstoss gegen das Rechtsmissbrauchsverbot gegeben ist, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.1.2 bis 1.1.5 S. 148 ff. mit Hinweisen). Auf die frist- und formgerecht eingereichte Beschwerde ist somit grundsätzlich einzutreten.
1.4 Soweit sich die Eingabe des Beschwerdeführers indessen gegen die Abweisung des Gesuchs um Erteilung einer Härtefallbewilligung gestützt auf Art. 30 Abs. 1 lit. b AuG richtet, kann darauf nicht eingetreten werden. Dagegen steht die Beschwerde an das Bundesgericht nicht offen.
1.5 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>).
2. Der Beschwerdeführer macht eine Verletzung des Rechtsverzögerungsverbots (<ref-law>) geltend. Seine Rüge beschränkt sich jedoch im Wesentlichen auf die Feststellung, das Gesuch um Verlängerung der Aufenthaltsbewilligung bzw. um Erteilung der Niederlassungsbewilligung sei am 19. Dezember 2002 gestellt und erst mit Verfügung vom 5. April 2006 bzw. mit Entscheid des Regierungsrates vom 31. März 2009 abgewiesen worden.
Es trifft zwar zu, dass die Sicherheitsdirektion sowie der Regierungsrat relativ lange zur Erledigung des Streitfalles benötigten. Eine eigentliche Rechtsverzögerung oder -verweigerung liegt aber nicht vor, nachdem der Entscheid nunmehr gefallen ist. Der Beschwerdeführer legt zudem nicht dar, inwiefern er durch die geltend gemachte überlange Verfahrensdauer in seinen Rechten beeinträchtigt worden sein oder Nachteile erlitten haben sollte, zumal seine Anwesenheit in der Schweiz während des vorinstanzlichen - wie im Übrigen auch des bundesgerichtlichen - Verfahrens zumindest prozessual geduldet war. Im Gegensatz etwa zu einem Familiennachzugsverfahren, wo die Beteiligten in dem für sie ungewünschten Zustand ausharren müssen, kommt eine lange Verfahrensdauer betreffend Nichtverlängerung einer Anwesenheitsbewilligung eher dem Ausländer entgegen. Die entsprechende Rüge erfüllt somit die Anforderungen an die nötige Begründung einer Beschwerde an das Bundesgericht nach Art. 42 Abs. 2 in Verbindung mit <ref-law> nicht, weshalb darauf nicht einzutreten ist.
Im Übrigen kann der Beschwerdeführer weder aus seiner durch die beanstandete Dauer des Verfahrens verlängerten Anwesenheit noch aus der verfahrensbedingten, längere Zeit dauernden Ungewissheit betreffend seinen zukünftigen Aufenthalt einen Anspruch auf einen weiteren Verbleib in der Schweiz ableiten.
3. 3.1 Gemäss Art. 7 Abs. 1 ANAG (in der Fassung vom 23. März 1990) hat der ausländische Ehegatte eines Schweizer Bürgers - wie erwähnt (E. 1.3) - Anspruch auf Verlängerung der Aufenthaltsbewilligung bzw. nach fünf Jahren auf Erteilung der Niederlassungsbewilligung. Kein Anspruch besteht, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern zu umgehen (Art. 7 Abs. 2 ANAG). Hierunter fällt die sogenannte Scheinehe oder Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen. Doch auch wenn eine Ehe nicht bloss zum Schein eingegangen worden ist, heisst das nicht zwingend, dass dem ausländischen Ehepartner der Aufenthalt ungeachtet der weiteren Entwicklung gestattet werden muss. Zu prüfen ist, ob sich die Berufung auf die Ehe nicht als rechtsmissbräuchlich erweist. Nach gefestigter bundesgerichtlicher Rechtsprechung liegt Rechtsmissbrauch vor, wenn der Ausländer sich im fremdenpolizeilichen Verfahren auf eine Ehe beruft, welche nur (noch) formell besteht oder aufrecht erhalten wird, mit dem alleinigen Ziel, ihm eine Anwesenheitsberechtigung zu ermöglichen; dieses Ziel wird von Art. 7 ANAG nicht geschützt (<ref-ruling> E. 4.2 S. 267; <ref-ruling> E. 4.2 S. 117, je mit Hinweisen).
3.2 Dass die Ehe nur noch formell und ohne Aussicht auf Wiederaufnahme einer ehelichen Gemeinschaft besteht, entzieht sich in der Regel dem direkten Beweis und ist bloss durch Indizien zu erstellen (BGE <ref-ruling> E. 10.2 und 10.3 S. 135 f. mit Hinweis). Feststellungen über das Bestehen solcher Indizien können äussere Gegebenheiten, aber auch innere, psychische Vorgänge betreffen (Wille der Ehegatten); es handelt sich so oder anders um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (oben E. 1.3). Frei zu prüfen ist die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe bezwecke die Umgehung fremdenpolizeilicher Vorschriften oder sei rechtsmissbräuchlich (<ref-ruling> E. 2.3 S. 152 mit Hinweisen).
3.3 Gemäss den Feststellungen der Vorinstanz war die Ehe des Beschwerdeführers bereits vor Ablauf der Fünfjahresfrist definitiv gescheitert. Hinweise darauf, 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. Die Ehegatten heirateten am 7. Juli 1998. Bereits Ende Dezember 1998 gab die Ehefrau dem Personalmeldeamt der Stadt Zürich an, sie wisse nicht, wo sich der Beschwerdeführer aufhalte. Gemäss den Angaben des Beschwerdeführers lebte er vom 7. Juli 1998 bis zum 27. Januar 1999 mit seiner Ehefrau zusammen, anschliessend zog diese aus und verbrachte längere Zeit in Afrika, ohne ihn über ihre Abwesenheit zu informieren. Auch nach ihrer Rückkehr verweigerte sie den Kontakt zum Beschwerdeführer. Mit Ausnahme der Angaben der Ehefrau anlässlich des Scheidungsverfahrens, wo sie mit für den Beschwerdeführer günstigeren Erklärungen - wie sie in der Folge nachvollziehbar darlegte - eine einvernehmliche Scheidung erreichen wollte, geht aus allen ihren Aussagen klar hervor, dass sie jedenfalls schon seit langem keinen Kontakt mehr mit dem Beschwerdeführer hatte, eine Weiterführung der Ehe für sie nicht in Frage kam und sie sich so schnell wie möglich scheiden lassen wollte. Weder aus der Abweisung der auf eine unheilbare Zerrüttung der Ehe gemäss alt <ref-law> gestützten Scheidungsklage der Ehefrau durch das Bezirksgericht Bülach am 3. Februar 2000 noch aus der nachfolgenden Verlängerung der Aufenthaltsbewilligung des Beschwerdeführers kann auf eine damals tatsächlich bestehende eheliche Gemeinschaft geschlossen werden. Derartiges kann auch nicht aus der finanziellen Unterstützung der Ehefrau durch den Beschwerdeführer abgeleitet werden; wird doch oft gerade auch bei Ausländerrechtsehen bzw. bei bloss zu ausländerrechtlichen Zwecken aufrecht erhaltenen Ehen, vom interessierten Ausländer eine finanzielle Abgeltung geleistet. Am 12. Februar 2004 wurde die Ehe sodann vom Bezirksgericht Zürich rechtskräftig geschieden, ohne dass das eheliche Zusammenleben je wieder aufgenommen worden wäre oder sonst in irgend einem Zeitpunkt konkrete Anzeichen für eine Versöhnung ersichtlich gewesen wären. Insgesamt bestehen somit gewichtige Indizien dafür, dass die Ehe, lange bevor ein Anspruch auf Niederlassungsbewilligung entstehen konnte, nur (noch) formell bestand.
Was der Beschwerdeführer dagegen einwendet, vermag diese Würdigung nicht zu erschüttern. Seine Behauptung, die Eheleute hätten immer wieder einen gemeinsamen Nenner gefunden und sich versöhnt, ist in keiner Weise belegt. Vielmehr mangelte es seit langem am Ehewillen der Ehegattin. So musste auch für den Beschwerdeführer seit geraumer Zeit erkennbar sein, dass mit einer Wiederaufnahme des gemeinsamen Haushalts nicht mehr gerechnet werden konnte, umso mehr als die Eheleute - wenn überhaupt - nur kurze Zeit in ehelicher Gemeinschaft gelebt hatten, jedenfalls schon mehrere Jahre getrennt lebten und keinen Kontakt pflegten. Konkrete Anhaltspunkte dafür, dass noch bis zum Ablauf der Fünfjahresfrist berechtigte Hoffnung auf Wiederaufnahme des Ehelebens bestand, macht auch der Beschwerdeführer nicht geltend.
3.4 Das Verwaltungsgericht des Kantons Zürich geht in seinem Entscheid von der dargelegten Rechtsprechung zur missbräuchlichen Berufung auf die Ehe aus. Bei gesamthafter Betrachtung aller Indizien musste sich der Schluss aufdrängen, dass keine Aussichten auf Wiederaufnahme einer echten ehelichen Gemeinschaft mehr bestanden und die Ehe definitiv gescheitert war. Von einer willkürlichen Beweiswürdigung kann nicht die Rede sein. Wenn sich der Beschwerdeführer unter den dargelegten Umständen dennoch auf die Ehe beruft, um eine Verlängerung der Aufenthaltsbewilligung bzw. Erteilung einer Niederlassungsbewilligung zu erwirken, handelt er rechtsmissbräuchlich. Wie die Vorinstanz zutreffend feststellt, kann der Beschwerdeführer auch aus dem Umstand, dass seine Aufenthaltsbewilligung trotz bestehender Zweifel während des formellen Bestands der Ehe zweimal verlängert wurde, keinen Anspruch auf weiteren Verbleib ableiten. Der Vorwurf, die Ausländerbehörde habe sich widersprüchlich verhalten, ist unberechtigt. Nach den damals geltenden ausländerrechtlichen Bestimmungen war die Verlängerung der Aufenthaltsbewilligung die Regel, solange die Ehe formell bestand. Die angefochtene Verweigerung der Niederlassungsbewilligung bzw. Nichtverlängerung der Aufenthaltsbewilligung verstösst somit nicht gegen Bundesrecht. Weitere Ausführungen dazu erübrigen sich. Es genügt, ergänzend auf die Erwägungen im angefochtenen Entscheid zu verweisen.
3.5 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 in der Schweiz ist daher nicht einzugehen. Diese könnten allenfalls bei der Prüfung der Erteilung einer Härtefallbewilligung bzw. 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 (vgl. E. 1.1).
4. 4.1 Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
4.2 Bei diesem Verfahrensausgang wird der Beschwerdeführer kostenpflichtig (Art. 66 Abs. 1 <ref-law>).

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, dem Regierungsrat und dem Verwaltungsgericht (2. Kammer) des Kantons Zürich sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 26. Oktober 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Zünd Dubs