Sachverhalt: A. X._ (geb. 1979) stammt aus Nigeria. Er reiste erstmals im Jahr 2000 unter falscher Identität in die Schweiz ein und stellte ein Asylgesuch, auf welches zuletzt die Schweizerische Asylrekurskommission nicht eintrat. Am 24. Januar 2002 heiratete er die Schweizerin Y._ (geb. 1980), worauf ihm eine bis im Oktober 2010 verlängerte Aufenthaltsbewilligung erteilt wurde. Am 9. September 2002 wurde die Ehe gerichtlich getrennt. Am 19. September 2002 kam die gemeinsame Tochter A.Y._ zur Welt. Im September 2003 ordnete die damals zuständige Vormundschaftsbehörde (heute Kindes- und Erwachsenenschutzbehörde) Kindesschutzmassnahmen an: Eine Beistandschaft wurde errichtet und die Obhut, d.h. das Recht, über den Aufenthaltsort des Kindes zu bestimmen, wurde den Eltern entzogen. Mit Urteil vom 25. Januar 2006 wurde die Ehe geschieden. Die Tochter A.Y._ wurde unter die elterliche Sorge von X._ gestellt. Die von der Vormundschaftsbehörde im September 2003 angeordneten Kindesschutzmassnahmen dauerten fort. Aus der Beziehung von X._ und der italienischen Staatsangehörigen Z._, welche er im Sommer 2002 kennengelernt hatte, ging am 4. Mai 2004 der gemeinsame Sohn B.Z._ hervor. B. Während seiner Anwesenheit in der Schweiz wurde X._ insgesamt dreizehn Mal strafrechtlich verurteilt. Hierunter fielen eine Verurteilung zu 80 Tagen Gefängnis wegen mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz (2. Dezember 2003); eine Verurteilung zu 60 Tagessätzen à Fr. 30.-- wegen mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz (21. Mai 2008), eine Verurteilung zu einer Freiheitsstrafe von 12 Monaten als Gesamtstrafe wegen Vergehens gegen das Betäubungsmittelgesetz (9. April 2010) sowie die Verurteilung zu einer Freiheitsstrafe von sechs Monaten und zu einer Geldstrafe von 60 Tagessätzen à Fr. 50.-- wegen mehrfacher Hinderung einer Amtshandlung sowie Vergehens gegen das Betäubungsmittelgesetz (28. Oktober 2011). Weitere Straferkenntnisse ergingen unter anderem wegen Hehlerei (2000; 10 Tage Gefängnis bedingt), wegen Sachbeschädigung (2003; 10 Tage Gefängnis bedingt) und wegen vorsätzlicher einfacher Körperverletzung (2006; 14 Tage Gefängnis). X._ wurde 2004, 2006 und 2007 ausländerrechtlich verwarnt. C. Im Oktober 2010 ersuchte X._ um Verlängerung der Aufenthaltsbewilligung bzw. Erteilung der Niederlassungsbewilligung. Mit Verfügung vom 24. Januar 2011 lehnte das Migrationsamt des Kantons Zürich dieses Gesuch vollständig ab. Ein hiergegen gerichteter Rekurs an die Sicherheitsdirektion des Kantons Zürich blieb ohne Erfolg (Urteil vom 13. April 2012). Die daraufhin erhobene Beschwerde an das Verwaltungsgericht wies dieses mit Urteil vom 3. Oktober 2012 ab. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 7. November 2012 beantragt X._ dem Bundesgericht, den Entscheid des Verwaltungsgerichts vom 3. Oktober 2012 aufzuheben. Eventuell sei die Streitsache zur weiteren Sachverhaltsabklärung zurückzuweisen. Das Verwaltungsgericht des Kantons Zürich hat auf eine Vernehmlassung verzichtet. Das Bundesamt für Migration beantragt, die Beschwerde abzuweisen. Mit Verfügung vom 22. November 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.