Sachverhalt:
A. X._ (geb. 1978) ist nigerianischer Staatsangehöriger. Er reiste am 5. Dezember 2003 unter Angabe von falschen Personalien in die Schweiz ein und stellte ein Asylgesuch, auf welches das damalige Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) mit Entscheid vom 19. August 2004 nicht eintrat. Mangels gültiger Reisepapiere konnte die Wegweisung jedoch nicht vollzogen werden. Am 19. Juli 2005 heiratete X._ eine Schweizer Bürgerin mit Jahrgang 1956 und erhielt in der Folge eine Aufenthaltsbewilligung. Nach der Aufhebung des gemeinsamen Haushaltes der Eheleute am 7. März 2006 wurde die Aufenthaltsbewilligung vom Migrationsamt des Kantons Zürich zur Abklärung der Verhältnisse bis zum 18. Juli 2007 verlängert.
B. Am 12. Dezember 2005 anerkannte X._ den im Juni 2005 geborenen Z._ als sein Kind. Dieser stammt aus einer Beziehung mit Y._ (geb. 1985), welche Schweizer Bürgerin ist. Die Vormundschaftsbehörde der Stadt Winterthur genehmigte in der Folge einen Unterhaltsvertrag und räumte dem Kindsvater ein begleitetes Besuchsrecht ein. Das Besuchsrecht wurde mit Beschluss des Obergerichts des Kantons Zürich vom 21. Januar 2008 bestätigt.
C. Das Migrationsamt wies das Gesuch von X._ um Verlängerung der Aufenthaltsbewilligung mit Verfügung vom 6. September 2007 ab. Ein hiegegen beim Regierungsrat des Kantons Zürich erhobener Rekurs blieb erfolglos. Mit Urteil vom 20. August 2008 wies das Verwaltungsgericht des Kantons Zürich die gegen den regierungsrätlichen Beschluss vom 5. März 2008 erhobene Beschwerde ab. Zur Begründung führte das Verwaltungsgericht aus, der Beschwerdführer berufe sich in rechtsmissbräuchlicher Weise auf eine nur noch formell bestehende Ehe; zudem bestehe keine besonders intensive Vater-Sohn-Beziehung, womit sich die Nichtverlängerung der Aufenthaltsbewilligung auch unter dem Blickwinkel von Art. 8 EMRK als verhältnismässig erweise.
D. Mit Eingabe vom 29. September 2008 erhebt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Er beantragt, den vorinstanzlichen Entscheid (sowie die unterinstanzlichen Verfügungen) aufzuheben und dem Beschwerdeführer den weiteren Aufenthalt in der Schweiz zu gestatten; eventualiter sei der Entscheid aufzuheben und die Streitsache zur weiteren Sachverhaltsabklärung zurückzuweisen. Gerügt wird eine unrichtige Feststellung des Sachverhalts, die Verletzung des rechtlichen Gehörs sowie des Rechts auf Familienleben (<ref-law> und Art. 8 EMRK). Sodann ersucht er um die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
E. Das Verwaltungsgericht sowie der Regierungsrat des Kantons Zürich und das Bundesamt für Migration beantragen die Abweisung der Beschwerde.
F. Mit Verfügung vom 3. Oktober 2008 erteilte der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung.

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 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 Da der Beschwerdeführer getrennt von seiner Ehefrau lebt und die Ehe offenbar mittlerweile rechtskräftig geschieden ist, hat er keinen Bewilligungsanspruch gestützt auf Art. 7 Abs. 1 ANAG. Hingegen ist der Sohn des Beschwerdeführers Schweizer Bürger und verfügt demnach über ein gefestigtes Anwesenheitsrecht in der Schweiz. Zu diesem hat der Beschwerdeführer eine Vater-Sohn-Beziehung aufgenommen, welche intakt scheint und im Rahmen der Möglichkeiten auch gelebt wird. Da er eine familiäre Beziehung zu seinem Sohn pflegt, hat er gestützt auf Art. 8 EMRK einen (bedingten) Rechtsanspruch auf eine Aufenthaltsbewilligung (<ref-ruling> E. 1e S. 5 mit Hinweisen).
Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist demzufolge einzutreten. Ob die Bewilligung verweigert werden durfte, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (vgl. <ref-ruling> E. 1.1.5 S. 150 mit Hinweisen).
1.4 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. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254). Eine qualifizierte Rügepflicht gilt u.a. hinsichtlich der Verletzung von Grundrechten. Das Bundesgericht prüft solche Rügen nur, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254 mit Hinweisen).
1.5 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). 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 <ref-law> beruht (Art. 97 Abs. 1 bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
1.6 Anfechtungsobjekt ist einzig das Urteil des Verwaltungsgerichts des Kantons Zürich. Soweit vorliegend auch die unterinstanzlichen Verfügungen angefochten werden, ist daher auf die Beschwerde nicht einzutreten.
2. Vorab rügt der Beschwerdeführer eine unrichtige Feststellung des Sachverhalts sowie die Verletzung des rechtlichen Gehörs.
2.1 Der Beschwerdeführer macht geltend, die Vorinstanz habe den Sachverhalt willkürlich festgestellt, weil sie die hypothetische künftige Entwicklung der Vater-Sohn-Beziehung nicht weiter abgeklärt, insbesondere keinen Bericht zum geplanten Vollzug des Besuchsrechts eingeholt sowie die Akten des Jugendsekretariats nicht beigezogen habe. Der Beschwerdeführer habe vor der Vorinstanz ausgeführt, es sei eine rasche Intensivierung des Kontakts geplant, "um die Vater-Sohn-Beziehung im normalen Rahmen der getrennten Elternsituation leben zu können". Der Beschwerdeführer verkennt damit aber, dass eine "normale" Beziehung zu einem Kind, dessen Betreuung nicht dem betreffenden Elternteil obliegt, noch kein Recht auf Erteilung der Aufenthaltsbewilligung verleiht (vgl. E. 3.2 und 3.3). Daraus ergibt sich, dass die Vorinstanz das entsprechende Beweisanerbieten in zulässiger antizipierter Beweiswürdigung als unerheblich betrachten durfte (vgl. <ref-ruling> E. 3 S. 157 mit Hinweisen), ohne dass darin eine Gehörsverweigerung erblickt werden könnte.
2.2 Der Beschwerdeführer rügt weiter eine Verletzung des rechtlichen Gehörs, weil die Vorinstanz die "Spezialität des Falles" nicht untersucht bzw. die konkreten Umstände (Erstreiten des Besuchs- und Kontaktrechts und Schwierigkeiten beim Vollzug) nicht untersucht habe. Im Ergebnis wird auch damit die Unzulänglichkeit der Sachverhaltsfeststellungen gerügt. Diese können allerdings nur dann mit Erfolg als mangelhaft bezeichnet werden, wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (vgl. E. 1.5), wobei der Beschwerdeführer darzulegen hat, inwiefern dies der Fall sein soll. Vorliegend hat der Beschwerdeführer diese Gründe nicht rechtsgenüglich dargelegt, weshalb auf die Rüge nicht einzutreten ist. Im Übrigen ist ohnehin nicht ersichtlich, inwiefern die Schwierigkeiten zur Kontaktaufnahme und Etablierung eines Besuchsrechts den Verfahrensausgang beeinflussen könnten. Entscheidend ist, wie intensiv die Vater-Sohn-Beziehung ist und nicht, aus welchen Gründen sie nur ein bestimmtes Niveau erreicht und nicht überschritten hat.
3. 3.1 Art. 8 EMRK - sowie seit dem 1. Januar 2000 auch <ref-law> (vgl. <ref-ruling> E. 7 S. 394) - gewährleisten das Recht auf Achtung des Privat- und Familienlebens. Hat ein Ausländer nahe Verwandte mit einem gefestigten Anwesenheitsrecht in der Schweiz und wird die intakte familiäre Beziehung zu diesen tatsächlich gelebt, kann es die entsprechenden Garantien verletzen, wenn ihm der Verbleib in der Schweiz untersagt und damit das Familienleben vereitelt wird (<ref-ruling> E. 3.1 S. 285). Der Beschwerdeführer beruft sich in diesem Zusammenhang auf seine familiären Bindungen zu seinem Sohn Z._, insbesondere auf die dank des Besuchsrechts aufgebaute Vater-Sohn-Beziehung.
3.2 Zunächst ist festzuhalten, dass der nicht sorgeberechtigte Ausländer die familiäre Beziehung zu seinem Kind zum Vornherein nur in einem beschränkten Rahmen, nämlich durch Ausübung des ihm eingeräumten Besuchsrechts, leben kann; dazu ist regelmässig nicht erforderlich, dass er sich dauernd im gleichen Land aufhält wie das Kind. Es ist daher im Allgemeinen zulässig, dem Ausländer, der gegenüber seinem in der Schweiz anwesenheitsberechtigten Kind bloss über ein Besuchsrecht verfügt, die Aufenthaltsbewilligung zu verweigern. Den Anforderungen von Art. 8 EMRK ist Genüge getan, wenn er das Besuchsrecht im Rahmen von Kurzaufenthalten vom Ausland her ausüben kann, wobei allenfalls dessen Modalitäten geeignet aus- bzw. umzugestalten sind. Die Aufenthaltsbewilligung ist nach der bundesgerichtlichen Rechtsprechung nur dann zu erteilen oder zu erneuern, wenn in wirtschaftlicher und affektiver Hinsicht eine besonders enge Beziehung zum Kind besteht, diese wegen der Distanz zum Heimatland des Ausländers praktisch nicht mehr aufrechterhalten werden könnte und das bisherige Verhalten des Betroffenen in der Schweiz zu keinerlei Klagen Anlass gegeben hat ("tadelloses Verhalten", "comportement irréprochable", "comportamento irreprensibile"; <ref-ruling> E. 3c S. 5, 22 E. 4a/b S. 25 f.; Urteile 2A.110/2007 vom 2. August 2007 E. 3.4; 2A.501/2006 vom 14. November 2006 E. 2.3.2 je mit Hinweisen).
3.3 Was das Erfordernis der besonderen Intensität der affektiven Beziehung betrifft, ist dieses regelmässig bloss dann als erfüllt zu erachten, wenn ein grosszügig ausgestaltetes Besuchsrecht eingeräumt ist und dieses kontinuierlich, spontan und reibungslos ausgeübt wird (vgl. Urteile 2A.110/2007 vom 2. August 2007 E. 3.4; 2A.77/2006 vom 15. Februar 2006, E.2.2.1; 2A.412/1998 vom 15. Dezember 1998, E. 3a).
Diese Voraussetzungen sind vorliegend nicht erfüllt: Der Beschwerdeführer versucht zwar, seine Beziehung zum Sohn möglichst normal zu gestalten. Von einer besonders engen Beziehung kann aber keine Rede sein. Dazu kommt, dass die Umstände seiner Anwesenheit (illegale Einreise, Angabe falscher Personalien, Nichtverlassen des Landes, Heirat mit einer um 22 Jahre älteren Schweizer Bürgerin zwecks Erwirkung der Aufenthaltsbewilligung, Verstösse gegen ANAG resp. SVG) nicht erlauben, ihm ein tadelloses Verhalten zu attestieren. Der Beschwerdeführer hat vielmehr den Eindruck entstehen lassen, er versuche mit allen - auch unerlaubten - Mitteln, einen Aufenthaltstitel in der Schweiz zu erlangen. Namentlich besteht in Fällen wir hier, in denen eine Vater-Sohn-Beziehung nicht als besonders intensiv bezeichnet werden kann, entgegen den Ausführungen des Beschwerdeführers keine "positive Pflicht des Staates auf Erteilung der Aufenthaltsbewilligung". Die Vater-Sohn-Beziehung kann auch vom Ausland her aufrechterhalten werden.
Aus dem Übereinkommen vom 20. November 1989 über die Rechte des Kindes (UNO-KRK; SR 0.107) ergeben sich im Übrigen im vorliegenden Fall angesichts des Fehlens einer besonders engen Beziehung zum Sohn keine über Art. 8 EMRK hinausgehenden Bewilligungsansprüche (vgl. Urteil 2A.472/2006 vom 11. Oktober 2006, E. 1.2).
3.4 Aus dem Umstand, dass der Sohn des Beschwerdeführers nicht nur über die schweizerische, sondern auch die italienische Staatsbürgerschaft verfügt, kann der Beschwerdeführer nichts für sich ableiten.
Die dargelegte Auslegung und Anwendung von Art. 8 EMRK ist - entgegen den Ausführungen des Beschwerdeführers - auch nicht auf eigentliche Missbrauchsfälle beschränkt. Vielmehr wird ein Aufenthaltsrecht gestützt auf diese Bestimmung in allen Fällen verweigert, in denen dieses nicht unabdingbar ist, um eine Vater-Sohn-Beziehung im tatsächlich gelebten Rahmen aufrecht zu erhalten.
4. Daraus ergibt sich, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen ist, soweit darauf eingetreten werden kann.
Bei diesem Verfahrensausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>); seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann mangels ernsthafter Erfolgsaussichten der Beschwerde nicht entsprochen werden (vgl. <ref-law>). Der wirtschaftlichen Situation des Beschwerdeführers wird indessen bei der Bemessung der Gerichtskosten Rechnung getragen.

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