Sachverhalt:
A. Der aus Algerien stammende X._ (geb. 1972) reiste 1997 in die Schweiz ein und ersuchte erfolglos um Asyl, worauf ihm eine Ausreisefrist bis zum 15. November 1998 angesetzt wurde. Am 23. Februar 1999 heiratete er eine 1931 geborene Schweizer Bürgerin. Gestützt auf die Heirat wurde X._ eine Aufenthaltsbewilligung erteilt.
Die Eheleute lebten zunächst in der Alterswohnung der Ehegattin. Im Juni 2000 zog X._ aus der nur für eine Person bestimmten Wohnung aus und lebt seither getrennt von seiner Ehefrau. Die Eheleute erklärten gegenüber dem Migrationsamt des Kantons Zürich wiederholt, dass ihre Ehe weiterhin gelebt werde und sie ihre Beziehung pflegten, indem sie fast täglich miteinander telefonierten und sich wöchentlich mindestens einmal gegenseitig besuchten. Es sei eine Wiederaufnahme des ehelichen Zusammenlebens beabsichtigt, sobald sie eine neue gemeinsame Wohnung fänden, die für sie bezahlbar und hinsichtlich des auswärtigen Arbeitsortes des Ehemannes günstig gelegen wäre. Nachdem sich die Eheleute am 2. und 5. Februar 2004 erneut in diesem Sinne geäussert und eine Änderung der ehelichen Verhältnisse verneint hatten, wurde X._ am 10. Februar 2004 die Niederlassungsbewilligung für den Kanton Zürich erteilt.
Am 23. September 2004 wurde die Ehe geschieden; das Scheidungsurteil erwuchs am 26. Oktober 2004 in Rechtskraft. X._ heiratete am 14. Oktober 2004 in Algerien eine Landsfrau (geb. 1980), welche er angeblich über Weihnachten/Neujahr 2003/2004 in Algerien kennengelernt hatte. Diese ersuchte im November 2004 in Algerien um ein Visum zwecks Aufenthalt bei ihrem Ehemann in der Schweiz.
B. Mit Verfügung vom 27. Mai 2005 widerrief das Migrationsamt des Kantons Zürich die Niederlassungsbewilligung von X._ und wies das Gesuch seiner zweiten Ehefrau um Bewilligung der Einreise ab.
Der gegen diese Verfügung beim Regierungsrat des Kantons Zürich erhobene Rekurs blieb erfolglos. Auf Beschwerde hin bestätigte das Verwaltungsgericht des Kantons Zürich den regierungsrätlichen Beschluss vom 30. Mai 2007 mit Urteil vom 21. November 2007, soweit es darauf eintrat.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 10. Januar 2008 beantragt X._, "in Gutheissung der Beschwerde sei von einem Widerruf der Niederlassungsbewilligung abzusehen"; eventualiter sei Ziffer 1 des Dispositivs des Urteils des Verwaltungsgerichts bzw. Ziffer I und II des Beschlusses des Regierungsrates sowie Ziffer 1 und 2 der Verfügung des Migrationsamtes aufzuheben und die Sache an die Vorinstanz zurückzuweisen.
Die Staatskanzlei des Kantons Zürich (für den Regierungsrat) und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich verzichtet auf eine Vernehmlassung.
D. Am 15. Januar 2008 erkannte der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde - antragsgemäss - aufschiebende Wirkung zu.

Erwägungen:
1. 1.1 Gegen kantonal letztinstanzliche Entscheide über den Widerruf von Niederlassungsbewilligungen ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig (<ref-law> e contrario). Das vorliegende Rechtsmittel ist als solche entgegenzunehmen. Soweit damit auch teilweise die Aufhebung der erstinstanzlichen Verfügung des Migrationsamtes des Kantons Zürich vom 27. Mai 2005 bzw. des Beschlusses des Regierungsrates des Kantons Zürich vom 30. Mai 2007 beantragt wird, kann auf die Beschwerde nicht eingetreten werden (<ref-law>).
1.2 Am 1. Januar 2008 ist das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG; SR 142.20) in Kraft getreten. Vorliegend ist jedoch noch das Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG) massgebend (Art. 126 Abs. 1 AuG analog).
1.3 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 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 erweist (<ref-law>).
2. Vorab rügt der Beschwerdeführer, sein Anspruch auf rechtliches Gehör sei verletzt, weil es die Vorinstanz abgelehnt hätte, seine ehemalige Gattin sowie Y._ als Zeugen zu befragen.
2.1 Der verfassungsrechtliche Gehörsanspruch gebietet, die rechtzeitig und formrichtig angebotenen Beweismittel abzunehmen, es sei denn, diese beträfen eine nicht erhebliche Tatsache oder seien offensichtlich untauglich, über die streitige Tatsache Beweis zu erbringen (<ref-ruling> E. 2 S. 242 mit Hinweisen). Eine vorweggenommene Beweiswürdigung wird dadurch nicht ausgeschlossen; der Richter kann das Beweisverfahren schliessen, wenn er aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 4a S. 469 mit Hinweisen). Art. 6 EMRK, auf den sich der Beschwerdeführer in diesem Zusammenhang ebenfalls beruft, findet auf den Widerruf einer Niederlassungsbewilligung keine Anwendung (vgl. VPB 61/1997 Nr. 121 S. 1009)
2.2 Der Regierungsrat hatte von einer persönlichen Befragung der nunmehr geschiedenen Ehefrau des Beschwerdeführers abgesehen, weil sich dieser im Rekursverfahren umfassend äussern konnte und seine frühere Ehefrau zu ihrer Ehe mehrmals Stellungnahmen abgegeben hatte. Das Verwaltungsgericht hat sich im angefochtenen Entscheid zum Antrag des Beschwerdeführers, im vorinstanzlichen Verfahren die ehemalige Ehefrau und Y._ als Zeugen einzuvernehmen, nicht explizit geäussert. Indem es aber von den beantragten Zeugeneinvernahmen abgesehen hat, hat es indirekt deren Relevanz verneint. Dies ist vertretbar. Die Vorinstanz hat zur Ermittlung des Standes der Ehe im Zeitpunkt der Erteilung der Niederlassungsbewilligung in tatsächlicher Hinsicht auf die Angaben des Beschwerdeführers vor dem Migrationsamt, seine Aussagen anlässlich der persönlichen Befragung durch die Scheidungsrichterin sowie auf die diversen Aussagen und schriftlichen Eingaben seiner ehemaligen Gattin abgestellt. Daraus ergab sich eine hinreichende Entscheidungsgrundlage, weshalb in antizipierter Beweiswürdigung auf eine erneute persönliche Anhörung der ehemaligen Ehefrau des Beschwerdeführers verzichtet werden durfte. Wenn schon der Beschwerdeführer hinsichtlich des Entstehungszeitpunktes des Scheidungswillens widersprüchliche Angaben machte (vgl. E. 3.3.2), bedurfte es hierzu im vorliegenden Zusammenhang nicht mehr der Einvernahme des angebotenen Zeugen Y._. Von einer Verletzung des Anspruchs des Beschwerdeführers auf rechtliches Gehör kann daher nicht die Rede sein.
3. 3.1 Gemäss Art. 7 Abs. 1 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung; des Weiteren hat er nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren Anspruch auf die Niederlassungsbewilligung. Kein Anspruch besteht, 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 (Art. 7 Abs. 2 ANAG). Erfasst wird davon die sogenannte Scheinehe bzw. Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen (<ref-ruling> E. 2.1 S. 151 mit Hinweisen). Der Anspruch entfällt darüber hinaus auch bei rechtsmissbräuchlicher Berufung auf eine nur noch formell und ohne Aussicht auf Aufnahme bzw. Wiederaufnahme einer ehelichen Gemeinschaft bestehende Ehe (<ref-ruling> E. 2.2 S. 151 mit Hinweisen). Als eigenes und selbständiges Niederlassungsrecht erlischt die einmal erteilte Niederlassungsbewilligung nicht mit der Auflösung der Ehe. Sie kann aber widerrufen werden.
3.2 Nach Art. 9 Abs. 4 lit. a ANAG kann eine Niederlassungsbewilligung widerrufen werden, wenn der Ausländer sie durch falsche Angaben oder wissentliches Verschweigen wesentlicher Tatsachen erschlichen hat. Der Widerruf setzt voraus, dass der Betroffene wissentlich falsche Angaben gemacht oder wesentliche Tatsachen verschwiegen hat, in der Absicht, gestützt darauf den Aufenthalt oder die Niederlassung bewilligt zu erhalten (Urteile 2A.33/2007 vom 9. Juli 2007, E. 4.1; 2A.129/2006 vom 27. Juni 2006, E.2.2; 2A.436/2003 vom 6. Januar 2004, E. 3.1; <ref-ruling> E. 3b S. 475 f.). Nach Art. 3 Abs. 2 ANAG ist der Ausländer verpflichtet, der Behörde über alles, was für den Bewilligungsentscheid massgebend sein kann, wahrheitsgetreu Auskunft zu geben. Wesentlich sind dabei nicht nur Umstände, nach denen die Fremdenpolizei ausdrücklich fragt, sondern auch solche, von denen der Gesuchsteller wissen muss, dass sie für den Bewilligungsentscheid relevant sind (Urteile 2A.511/2001 vom 10. Juni 2002, publ. in: Pra 2002 Nr. 163, E. 3.2; 2A.57/2002 vom 20. Juni 2002, publ. in: Pra 2002 Nr. 165, E. 2.2, je mit Hinweisen). Das Erschleichen einer Niederlassungsbewilligung durch falsche Angaben oder durch wissentliches Verschweigen von Tatsachen kann schon darin liegen, dass die Angaben, auf welche sich die Behörden bei der seinerzeitigen Erteilung der Aufenthaltsbewilligung gestützt hatten oder die bei späteren Verlängerungen der Aufenthaltsbewilligung oder bei der Erteilung der Niederlassungsbewilligung mangels anderer Angaben immer noch als massgebend betrachtet werden konnten, falsch oder unvollständig waren (Urteil 2A.511/2001 vom 10. Juni 2002, E. 3.2).
3.3 Das Verwaltungsgericht geht in seinem Urteil von der dargestellten Rechtsprechung aus und hat diese korrekt angewandt.
3.3.1 Der Beschwerdeführer versucht, die von den kantonalen Instanzen angeführten Indizien, die darauf schliessen lassen, dass der Ehewille des Beschwerdeführers schon vor Erteilung der Niederlassungsbewilligung nicht mehr bestanden hat, zu entkräften. Er macht geltend, dass nur zwei der von der Vorinstanz angeführten Indizien (Altersunterschied und kurzes Zusammenleben) im Zeitpunkt der Bewilligungserteilung vorgelegen hätten. Diese beiden Angaben habe der Beschwerdeführer weder verschwiegen noch falsch mitgeteilt. Die übrigen Indizien (Scheidung kurz nach der Erteilung der Niederlassungsbewilligung, neue Beziehung und Eheschliessung mit der jetzigen Ehegattin sowie einschlägige Aussagen des Beschwerdeführers im Scheidungsverfahren) bezögen sich ausschliesslich auf Gegebenheiten nach Erteilung der Niederlassungsbewilligung. Die Vorinstanz verfalle in Willkür, wenn sie aufgrund dieser späteren Ereignisse auf einen früheren Sachverhalt schliesse.
3.3.2 Die tatsächlichen Feststellungen des Verwaltungsgerichts (vgl. E. 1.3 und 2) und die daraus gezogenen Schlussfolgerungen sind indessen nicht zu beanstanden. Es mag zwar zutreffen, dass gewisse einzelne Umstände für sich allein genommen nicht genügen, um bereits auf das Vorliegen einer Täuschung zwecks Erschleichen einer fremdenpolizeilichen Bewilligung zu schliessen. Es kommt aber auf eine Gesamtbetrachtung an. Entgegen den Ausführungen des Beschwerdeführers kann daher auch auf Indizien abgestellt werden, die sich aus Tatsachen nach der Erteilung der Niederlassungsbewilligung ergeben.
Wie der Beschwerdeführer zu Recht ausführt, war der kantonalen Behörde bekannt, dass er mit seiner 41 Jahre älteren Ehefrau spätestens seit Juni 2000 nicht mehr zusammenlebte. Der Beschwerdeführer und seine damalige Ehefrau erklärten indessen wiederholt übereinstimmend, letztmals im Februar 2004, als sich aufgrund von Art. 7 Abs. 1 Satz 2 ANAG die Frage des Anspruchs auf Erteilung der Niederlassungsbewilligung an den Beschwerdeführer stellte, dass sie bei einer passenden Wohnung das eheliche Zusammenleben wieder aufnehmen würden und dass keine Scheidungsabsichten bestünden. Die Behörde verliess sich bei der Erteilung der Niederlassungsbewilligung am 10. Februar 2004 auf diese Auskünfte. Bereits am 12. Mai 2004 reichten die Eheleute ein gemeinsames Scheidungsbegehren ein. Gemäss Protokoll des Bezirksgerichtes Winterthur vom 8. Juli 2004 antwortete der Beschwerdeführer auf die Frage der Einzelrichterin, wann sein Wille, sich scheiden zu lassen, entstanden sei, er glaube, schon etwa vor einem Jahr oder schon im Jahr 2001. Wie das Verwaltungsgericht zu Recht erwogen hat, lässt sich aus dem Umstand, dass diese Aussage unpräzis ist, weil der Beschwerdeführer seine Unsicherheit in Bezug auf den Zeitpunkt zum Ausdruck bringt, nichts zu Gunsten des Beschwerdeführers ableiten. Vielmehr hat der Beschwerdeführer trotz der zeitlichen Ungenauigkeit damit klar zum Ausdruck gebracht, dass bereits vor Ablauf der Fünfjahresfrist gemäss Art. 7 ANAG sein Ehewille erloschen war und Scheidungsabsichten bestanden. Der Beschwerdeführer hätte bei wahrheitsgetreuer Darlegung der Verhältnisse keinen Anspruch auf die Niederlassungsbewilligung gehabt. Der Widerrufsgrund nach Art. 9 Abs. 4 lit. a ANAG ist somit erfüllt. Das Vorgehen des Beschwerdeführers (Erwirken einer Aufenthaltsbewilligung nach abgewiesenem Asylgesuch durch Heirat einer Schweizerin, Altersunterschied von 41 Jahren zwischen den Ehegatten, kurze Dauer des gemeinsamen Haushaltes, Scheidungsbegehren drei Monate nach Erteilung der Niederlassungsbewilligung, Heirat mit einer Landsfrau noch vor Eintritt der Rechtskraft des Scheidungsurteils) entspricht im Übrigen einem aus zahlreichen Verfahren bekannten Verhaltensmuster (vgl. dazu etwa Urteile 2C_492/2007 vom 11. Februar 2008 und 2A.129/2006 vom 27. Juni 2006).
Was der Beschwerdeführer dagegen vorbringt, ist nicht geeignet, das Vorliegen einer Täuschung zwecks Erschleichung einer fremdenpolizeilichen Bewilligung zu widerlegen. Abgesehen davon, dass sich die Belege für die (erfolglose) Wohnungssuche auf das Jahr 2000 beziehen, bedarf es diesbezüglich keiner weiteren Erörterungen, nachdem feststeht, dass der Beschwerdeführer gegenüber der Fremdenpolizeibehörde falsche Angaben gemacht hat, indem er erklärte, das eheliche Zusammenleben werde wieder aufgenommen und es bestünden keine Scheidungsabsichten.
3.3.3 Der Schluss der Vorinstanz, der Beschwerdeführer habe die Fremdenpolizeibehörde über den Fortbestand des Ehewillens getäuscht und die ihm erteilte Niederlassungsbewilligung im Sinne von Art. 9 Abs. 4 lit. a ANAG durch falsche Aussagen bzw. wissentliches Verschweigen seiner wahren Intentionen erschlichen, ist somit nicht zu beanstanden. Hätte der Beschwerdeführer seine Absicht, sich wenige Monate nach Erhalt der Niederlassungsbewilligung scheiden zu lassen, um eine Landsfrau zu heiraten und diese in die Schweiz nachzuziehen, den Behörden bekanntgegeben, wäre ihm die Niederlassungsbewilligung nicht erteilt worden.
4. Der Widerruf der Niederlassungsbewilligung ist unter den gegebenen Umständen auch verhältnismässig. Zwar scheint der Beschwerdeführer hier persönlich und beruflich integriert zu sein. Von einer eigentlichen Verwurzelung in der Schweiz kann jedoch nicht gesprochen werden. Der Beschwerdeführer lebte bis zum 25. Altersjahr in seiner Heimat und hat damit die prägenden Lebensjahre in Algerien verbracht, wo er auch den Jahreswechsel 2003/04 feierte. Es darf davon ausgegangen werden, dass der Beschwerdeführer mit den kulturellen und gesellschaftlichen Gepflogenheiten seines Heimatlandes nach wie vor bestens vertraut ist. Ins Gewicht fällt zudem, dass seine heutige Ehefrau sowie seine Familie dort leben. Dem Beschwerdeführer ist somit zuzumuten, nach Algerien zurückzukehren.
5. 5.1 Der verfügte Widerruf der Niederlassungsbewilligung ist folglich bundesrechtskonform. Die Beschwerde ist somit als unbegründet abzuweisen, soweit darauf eingetreten werden kann.
5.2 Bei diesem Verfahrensausgang wird der Beschwerdeführer kostenpflichtig (<ref-law>). Parteientschädigungen sind nicht geschuldet (<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, dem Migrationsamt des Kantons Zürich, dem Regierungsrat des Kantons Zürich, dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, 4. Kammer, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 7. Mai 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Merkli Dubs