Erwägungen:
1. 1.1 Der guineische Staatsangehörige X._ (geb. 1979) reiste im Jahr 1999 illegal in die Schweiz ein und stellte ein Asylgesuch, das am 2. April 2001 von der Schweizerischen Asylrekurskommission rechtskräftig abgewiesen wurde. Seiner Ausreisepflicht kam X._ nicht nach. Am 3. Mai 2004 heiratete er die Schweizerin A._ und erhielt in der Folge eine bis 2. November 2007 verlängerte Aufenthaltsbewilligung. Spätestens im November 2004 gaben die Eheleute die gemeinsame Wohnung auf; die Ehe wurde am 5. Januar 2011 geschieden.
X._ ist Vater zweier Töchter, die nicht aus der Beziehung mit A._ hervorgegangen sind: der am ... geborenen ghanaischen Staatsangehörigen C._ und der am ... geborenen B._, die seit dem Jahr 2007 Schweizer Bürgerin ist. Die Tochter C._ wurde inzwischen rechtskräftig aus der Schweiz weggewiesen.
X._ ist in den Jahren 2001 bis 2009 mehrfach strafrechtlich in Erscheinung getreten, unter anderem wegen Hehlerei, einfacher Körperverletzung und Widerhandlungen gegen das Betäubungsmittelgesetz. Daraus resultierten insgesamt sechs Verurteilungen zu Bussen, Geldstrafen und Freiheitsstrafen bis zu 15 Monaten.
1.2 Mit Verfügung vom 27. April 2011 wies das Migrationsamt des Kantons Zürich das Gesuch von X._ vom 9. Oktober 2007 um Verlängerung der Aufenthaltsbewilligung ab und wies ihn aus der Schweiz weg. Mit Rekurs vom 1. Juni 2011 beantragte X._ in der Hauptsache die Erteilung der Niederlassungsbewilligung. Die Sicherheitsdirektion des Kantons Zürich wies den Rekurs am 16. April 2012 ab. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich am 31. Juli 2012 ab.
1.3 Vor Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 31. Juli 2012 aufzuheben und ihm die Niederlassungsbewilligung zu erteilen, eventualiter die Aufenthaltsbewilligung zu verlängern und den Vorinstanzen zu verbieten, ihn aus der Schweiz wegzuweisen. Subeventualiter seien weitere Sachabklärungen vorzunehmen bzw. vornehmen zu lassen.
Das Verwaltungsgericht des Kantons Zürich verzichtete auf eine Vernehmlassung. Die Sicherheitsdirektion des Kantons Zürich und das Bundesamt für Migration beantragen die Abweisung der Beschwerde.
2. 2.1 Am 1. Januar 2008 ist das Ausländergesetz (AuG; SR 142.20) unter Aufhebung des zuvor geltenden Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121 sowie Änderungen gemäss Fussnote zu Ziff. I des Anhangs 2 zum AuG) in Kraft getreten (AS 2007 5489). Gemäss Art. 126 Abs. 1 AuG bleibt das frühere materielle Recht aber anwendbar auf Gesuche, die vor dem 1. Januar 2008 eingereicht worden sind.
Der Beschwerdeführer hat sein Gesuch um Verlängerung der Aufenthaltsbewilligung am 9. Oktober 2007 gestellt, sodass auf das vorliegende Verfahren grundsätzlich das frühere materielle Recht anwendbar bleibt, auch wenn die Scheidung erst nach Inkrafttreten des AuG erfolgt ist (Urteil 2C_241/2009 vom 23. September 2009 E. 2). Ob jedoch auf die erstmals in der Rekursschrift vom 1. Juni 2011 beantragte Erteilung der Niederlassungsbewilligung das neue Recht anwendbar ist (Urteil 2C_241/2009 vom 23. September 2009 E. 2; vgl. aber auch Urteile 2C_771/2009 vom 1. Februar 2010 E. 1; 2C_142/2009 vom 20. Juli 2009 E. 1), kann vorliegend offenbleiben, da das für die materielle Beurteilung ausschlaggebende Kriterium nicht geändert hat (dazu E. 3.3).
2.2 Der Beschwerdeführer beruft sich unter anderem auf Art. 42 Abs. 3 AuG bzw. Art. 7 ANAG sowie auf Art. 8 EMRK und macht in vertretbarer Weise einen Bewilligungsanspruch geltend, weshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist (<ref-law> e contrario; Urteil 2C_821/2011 vom 22. Juni 2012 E. 1, nicht publ. in: <ref-ruling>). Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten ist daher einzutreten.
2.3 Nicht einzutreten ist dagegen auf die hilfsweise erhobene subsidiäre Verfassungsbeschwerde. Zwar steht nur dieses Rechtsmittel gegen den kantonalen Wegweisungsentscheid offen (vgl. <ref-law>), doch begründet der Beschwerdeführer - entgegen der ihm obliegenden qualifizierten Rügepflicht (<ref-ruling> E. 3.3 S. 310) - nicht, dass und inwiefern der Wegweisungsentscheid als Konsequenz der Bewilligungsverweigerung selbständig gegen ein besonderes verfassungsmässiges Recht verstossen würde (vgl. Art. 116 i.V.m. Art. 117 und Art. 106 Abs. 2 BGG; <ref-ruling> ff.).
3. 3.1 Das Bundesgericht wendet das Recht von Amtes wegen an und kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (<ref-law>; <ref-ruling> E. 1.4.1 S. 254 mit Hinweisen). Seinem Urteil legt es grundsätzlich den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 5.1 S. 356).
3.2 Die vom Beschwerdeführer gegen das vorinstanzliche Urteil erhobenen Sachverhaltsrügen sind nicht entscheidrelevant, da der Anspruch auf eine Niederlassungsbewilligung - in Präzisierung der vorinstanzlichen Ausführungen - bereits daran scheitert, dass kein fünfjähriger ordnungsgemässer Aufenthalt vorliegt (dazu sogleich E. 3.3). Es erübrigt sich daher, näher darauf einzugehen, ob eine Scheinehe und/oder wichtige Gründe für das Getrenntleben vorlagen.
3.3 Sowohl nach altem Recht (vgl. Art. 7 Abs. 1 Satz 2 ANAG) wie nach neuem Recht (Art. 42 Abs. 3 AuG) setzt der Anspruch auf eine Niederlassungsbewilligung (unter anderem) einen ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren voraus: Ordnungsgemäss ist der Aufenthalt, wenn er ausländerrechtlich bewilligt ist, nicht hingegen, wenn er aufgrund eines laufenden Verfahrens lediglich toleriert wird, sofern der Ausgang des Rechtsstreits zu keiner Bewilligung führt (<ref-ruling> E. 4.4 S. 13 f. und E. 4.6 S. 15; ferner <ref-ruling> E. 4.3 S. 8; <ref-ruling> E. 3b S. 367; Urteile 2C_268/2011 vom 22. Juli 2011 E. 6.1; 2C_77/2011 vom 25. Mai 2011 E. 2.2; 2A.105/2001 vom 26. Juni 2001 E. 3). Unerheblich ist dabei, ob diese Tolerierung von Gesetzes wegen stattfindet oder behördlich bzw. richterlich angeordnet worden ist (vgl. <ref-ruling> E. 4.6 S. 15). Als ordnungsgemässer Aufenthalt wird bei in der Schweiz geschlossenen Ehen auch regelmässig die Zeit zwischen Heirat und Bewilligungserteilung betrachtet (<ref-ruling> E. 4.4 S. 14). Der Beschwerdeführer heiratete am 3. Mai 2004 und erhielt eine bis 2. November 2007 verlängerte Aufenthaltsbewilligung. Im Rahmen des erfolglosen Asylverfahrens wie auch seit dem 2. November 2007 wurde bzw. wird der Aufenthalt des Beschwerdeführers lediglich toleriert (vgl. <ref-ruling> E. 4.6 S. 15 f.). Daher besteht vorliegend kein Anspruch auf eine Niederlassungsbewilligung.
3.3 Sowohl nach altem Recht (vgl. Art. 7 Abs. 1 Satz 2 ANAG) wie nach neuem Recht (Art. 42 Abs. 3 AuG) setzt der Anspruch auf eine Niederlassungsbewilligung (unter anderem) einen ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren voraus: Ordnungsgemäss ist der Aufenthalt, wenn er ausländerrechtlich bewilligt ist, nicht hingegen, wenn er aufgrund eines laufenden Verfahrens lediglich toleriert wird, sofern der Ausgang des Rechtsstreits zu keiner Bewilligung führt (<ref-ruling> E. 4.4 S. 13 f. und E. 4.6 S. 15; ferner <ref-ruling> E. 4.3 S. 8; <ref-ruling> E. 3b S. 367; Urteile 2C_268/2011 vom 22. Juli 2011 E. 6.1; 2C_77/2011 vom 25. Mai 2011 E. 2.2; 2A.105/2001 vom 26. Juni 2001 E. 3). Unerheblich ist dabei, ob diese Tolerierung von Gesetzes wegen stattfindet oder behördlich bzw. richterlich angeordnet worden ist (vgl. <ref-ruling> E. 4.6 S. 15). Als ordnungsgemässer Aufenthalt wird bei in der Schweiz geschlossenen Ehen auch regelmässig die Zeit zwischen Heirat und Bewilligungserteilung betrachtet (<ref-ruling> E. 4.4 S. 14). Der Beschwerdeführer heiratete am 3. Mai 2004 und erhielt eine bis 2. November 2007 verlängerte Aufenthaltsbewilligung. Im Rahmen des erfolglosen Asylverfahrens wie auch seit dem 2. November 2007 wurde bzw. wird der Aufenthalt des Beschwerdeführers lediglich toleriert (vgl. <ref-ruling> E. 4.6 S. 15 f.). Daher besteht vorliegend kein Anspruch auf eine Niederlassungsbewilligung.
3.4 3.4.1 Mit der Scheidung der Ehe am 5. Januar 2011 entfiel der auf Art. 7 Abs. 1 ANAG gestützte Anspruch auf eine Aufenthaltsbewilligung. Eine dem Art. 50 AuG vergleichbare Regelung gab es im alten Recht nicht. Hingegen hat der nicht sorge- bzw. obhutsberechtigte Ausländer gestützt auf Art. 8 EMRK ausnahmsweise dann einen Anspruch auf Erteilung einer Aufenthaltsbewilligung, wenn zwischen ihm und seinem Kind in wirtschaftlicher und affektiver Hinsicht eine besonders enge Beziehung besteht, die - würde eine Bewilligung verweigert - wegen der Distanz zwischen der Schweiz und dem Land, in das der Ausländer vermutlich auszureisen hätte, praktisch nicht aufrechterhalten werden könnte. Zudem muss sich der Ausländer tadellos verhalten haben (Urteile 2C_467/2012 vom 25. Januar 2013 E. 2.1.5; 2C_382/2012 vom 7. Dezember 2012 E. 2.3). Über diese Rechtsprechung werden auch die Vorgaben des vom Beschwerdeführer angerufenen <ref-law> berücksichtigt (vgl. <ref-ruling> E. 2.2.2 S. 157; Urteil 2C_832/2010 vom 2. Februar 2011 E. 2.2.2). <ref-law> räumt keine weiter gehenden Ansprüche ein (Urteil 2C_382/2012 vom 7. Dezember 2012 E. 2.2).
3.4.2 Ein auf Art. 8 EMRK gestützter Bewilligungsanspruch scheitert beim Beschwerdeführer bereits daran, dass weder in wirtschaftlicher noch in affektiver Hinsicht eine besonders enge Beziehung zur Tochter besteht. Zwar hat sich die Vater-Tochter-Beziehung im Verlaufe des langjährigen Verfahrens gebessert, doch nimmt der Beschwerdeführer, der weiterhin über kein geregeltes Besuchsrechts verfügt, seine von der Kindesmutter eingeräumte Besuchsmöglichkeit nicht regelmässig wahr und kann seiner Pflicht zur Bezahlung der Unterhaltsbeträge nicht nachkommen. Hinzu kommt, dass es die zahlreichen Verurteilungen des Beschwerdeführers ausschliessen, sein Verhalten als tadellos zu bezeichnen. Inwieweit <ref-law> vorliegend weitergehende Ansprüche vermitteln soll, macht der Beschwerdeführer nicht rechtsgenüglich geltend (vgl. Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG).
3.4.3 Aufgrund des Gesagten überwiegt das öffentliche Interesse, den Aufenthalt des Beschwerdeführers zu beenden, sein privates Interesse am weiteren Aufenthalt in der Schweiz (vgl. Urteil 2C_382/2012 vom 7. Dezember 2012 E. 2.3). Die Rückkehr ins Heimatland ist dem Beschwerdeführer zumutbar. Die von ihm angerufenen Gesundheitsprobleme blieben bereits vor der Vorinstanz weitgehend unsubstanziiert. Erstellt ist die HIV-Erkrankung, wobei der Beschwerdeführer die für das Bundesgericht verbindlichen Feststellungen der Vorinstanz (vgl. <ref-law>) zum Krankheitsstadium wie zu den Behandlungsmöglichkeiten in Guinea nicht rechtsgenüglich bestreitet.
4. Aus den vorstehenden Erwägungen ergibt sich, dass die Eingabe offensichtlich unbegründet ist, soweit überhaupt darauf einzutreten ist. Sie ist daher im Verfahren nach <ref-law> abzuweisen. Dem Verfahrensausgang entsprechend wird der unterliegende Beschwerdeführer kostenpflichtig (vgl. <ref-law>). Seinem Gesuch um unentgeltliche Rechtspflege ist infolge Aussichtslosigkeit nicht zu entsprechen (<ref-law>). Es sind keine Parteientschädigungen geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
4. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
5. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 11. April 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Egli