Sachverhalt:
A. X._, geboren 1983, ist guineischer Staatsangehöriger. Am 5. November 2001 reiste er in die Schweiz ein und stellte unter falschem Namen erfolglos ein Asylgesuch. Nach einem Nichteintretensentscheid der damaligen Schweizerischen Asylrekurskommission (heute: Bundesverwaltungsgericht) vom 25. April 2002 setzte das damalige Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) X._ eine Frist bis zum 13. Mai 2002, um die Schweiz zu verlassen. Er kam der Ausreiseverpflichtung jedoch nicht nach, sondern blieb in der Schweiz und galt seit dem 20. Februar 2006 als verschwunden.
Am 3. März 2006 heiratete X._ die in der Schweiz niedergelassene kroatische Staatsangehörige Y._, geboren 1987. Daraufhin erhielt er die Aufenthaltsbewilligung zum Verbleib bei der Ehefrau, letztmals verlängert bis zum 2. März 2010. Die gemeinsame Tochter Z._ wurde am 13. Januar 2008 geboren; sie ist im Besitz einer Niederlassungsbewilligung.
Die Ehegatten beendeten das Zusammenleben am 25. April 2008. Nachdem Y._ ihr Trennungsbegehren beim Zivilgericht des Kantons Basel-Stadt zurückgezogen hatte, nahmen die Eheleute die Haushaltsgemeinschaft am 1. Mai 2009 wieder auf. Seit dem 1. Oktober 2009 leben sie dauerhaft getrennt. Am 4. Dezember 2009 übertrug das Zivilgericht des Kantons Basel-Stadt Y._ die elterliche Obhut über die Tochter Z._ und setzte die von X._ zu leistenden Unterhaltsbeiträge fest; über die Ausgestaltung der Besuchs- und Ferienkontakte zwischen Vater und Tochter würden sich die Parteien weiterhin in direkter Absprache einigen.
B. Am 3. März 2010 unterbreitete das Migrationsamt des Kantons Basel-Stadt (nachfolgend: Migrationsamt) dem Bundesamt für Migration das Gesuch um Zustimmung zur Verlängerung der Aufenthaltsbewilligung von X._. Nach Gewährung des rechtlichen Gehörs verweigerte das Bundesamt für Migration am 8. Juni 2010 die Zustimmung zur Verlängerung der Aufenthaltsbewilligung und wies X._ aus der Schweiz weg.
Das Bundesverwaltungsgericht wies die dagegen erhobene Beschwerde mit Urteil vom 29. März 2012 ab.
C. Mit Beschwerde an das Bundesgericht vom 9. Mai 2012 beantragt X._, das Urteil des Bundesverwaltungsgerichts aufzuheben und die Aufenthaltsbewilligung zu verlängern sowie die "Ausweisung" aus der Schweiz aufzuheben.
Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde, während das Bundesverwaltungsgericht auf eine Vernehmlassung verzichtet.

Erwägungen:
1. 1.1 Der verfahrensabschliessende Entscheid des Bundesverwaltungsgerichts in einer Angelegenheit des öffentlichen Rechts unterliegt grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten (vgl. <ref-law>, <ref-law>, <ref-law>). Gemäss <ref-law> ist die Beschwerde unzulässig gegen Entscheide auf dem Gebiet des Ausländerrechts betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Vorliegend kann sich der Beschwerdeführer, welcher in der Schweiz eine Tochter mit Niederlassungsbewilligung hat, auf Art. 50 Abs. 1 lit. b AuG (SR 142.20) sowie auf Art. 8 Ziff. 1 EMRK berufen. Letzteres gilt auch für den ausländischen Elternteil, der - wie der Beschwerdeführer - weder über das Sorge- noch das Obhutsrecht gemäss <ref-law> verfügt (<ref-ruling> E. 1d S. 3). Vorausgesetzt wird, dass das in der Schweiz lebende Kind über ein gefestigtes originäres Anwesenheitsrecht verfügt (<ref-ruling> E. 1.3.1 S. 145 f.), was hier der Fall ist. Ob der Anspruch auf Verlängerung der Aufenthaltsbewilligung im konkreten Fall zu bejahen ist, wird im Rahmen der materiellen Behandlung der Beschwerde zu prüfen sein (<ref-ruling> E. 1.1 S. 179). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist zulässig, soweit sie sich auf die Nichtverlängerung der Aufenthaltsbewilligung bezieht.
Auf das sinngemäss gestellte Begehren, die Wegweisung sei aufzuheben, kann dagegen nicht eingetreten werden, da gemäss <ref-law> die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide betreffend die Wegweisung unzulässig ist (vgl. Urteil 2C_395/2012 vom 9. Juli 2012 E. 1). Auch die subsidiäre Verfassungsbeschwerde ist nicht gegeben, denn dieses Rechtsmittel steht gemäss <ref-law> nur gegen Entscheide letzter kantonaler Instanzen offen (Urteil 2C_769/2012 vom 22. Oktober 2012 E. 1.4).
1.2 Die übrigen Sachurteilsvoraussetzungen sind erfüllt, so dass - mit der genannten Einschränkung - auf die Beschwerde einzutreten ist.
2. 2.1 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 und Art. 96 BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (<ref-ruling> E. 1.4.1 S. 254). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 1.4.2 S. 254).
2.2 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur beanstandet bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinn von <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substanziiert vorzubringen ist (<ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
2.3 Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Tatsachen, welche sich erst nach Erlass des angefochtenen Entscheids ereignet haben (echte Noven), sind im bundesgerichtlichen Verfahren unzulässig, da sie von vornherein nicht durch den vorinstanzlichen Entscheid veranlasst sein können (Urteil 2C_833/2011 vom 6. Juni 2012 E. 1.2; <ref-ruling> E. 5.2.4 S. 229; <ref-ruling> E. 2.1 S. 344).
Der Arbeitsvertrag des Beschwerdeführers mit der W._ GmbH vom 22. Juni 2011 wurde erst im bundesgerichtlichen Verfahren eingereicht und stellt ein unechtes Novum dar. Inhaltlich stimmt der Vertrag jedoch mit den im vorinstanzlichen Verfahren eingereichten Lohnabrechnungen von November 2011 bis Januar 2012 überein, so dass auf die entsprechenden Löhne abgestellt werden kann. Die am 21. September 2012 vom Migrationsamt eingereichte Trauungsmitteilung des Zivilstandsamts Basel-Stadt vom 14. September 2012 ist als echtes Novum im vorliegenden Verfahren unbeachtlich.
2.4 Die anwendbaren Gesetzesbestimmungen und die Voraussetzungen zur Durchführung des Zustimmungsverfahrens vor dem Bundesamt für Migration wurden im angefochtenen Urteil korrekt dargelegt, so dass darauf verwiesen werden kann.
3. 3.1 Die Aufenthaltsbewilligung war dem Beschwerdeführer im Rahmen des Familiennachzugs nach Art. 43 Abs. 1 AuG erteilt worden. Danach haben ausländische Ehegatten von Personen mit Niederlassungsbewilligung Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen. Nach Auflösung der Ehe oder der Familiengemeinschaft besteht der Anspruch des Ehegatten auf Erteilung und Verlängerung der Aufenthaltsbewilligung weiter, wenn die Ehegemeinschaft mindestens 3 Jahre gedauert hat und eine erfolgreiche Integration besteht (Art. 50 Abs. 1 lit. a AuG) oder wichtige persönliche Gründe einen weiteren Aufenthalt in der Schweiz erforderlich machen (Art. 50 Abs. 1 lit. b AuG).
3.2 Der Beschwerdeführer macht vor Bundesgericht zu Recht nicht mehr geltend, die Ehegemeinschaft habe länger als drei Jahre bestanden. Die Vorinstanz hat einen Anspruch aus Art. 50 Abs. 1 lit. a AuG zutreffend verneint, so dass entsprechend dem Vorbringen des Beschwerdeführers zu prüfen ist, ob die Aufenthaltsbewilligung gestützt auf Art. 50 Abs. 1 lit. b AuG zu verlängern ist.
3.3 Wichtige Gründe im Sinn von Art. 50 Abs. 1 lit. b AuG können namentlich vorliegen, wenn die Ehegattin oder der Ehegatte Opfer ehelicher Gewalt wurde und die soziale Wiedereingliederung im Herkunftsland stark gefährdet erscheint (Art. 50 Abs. 2 AuG), wobei diese Aufzählung nicht abschliessend ist (<ref-ruling> E. 5.3). Das Vorhandensein gemeinsamer Kinder kann einen wichtigen persönlichen Grund darstellen, sofern die betroffene Person zu ihnen eine intakte Beziehung lebt und diese ihrerseits gut integriert sind (<ref-ruling> E. 2.3.1 S. 290; <ref-ruling> E. 3.2.2 S. 349; MARC SPESCHA, in: Migrationsrecht, Kommentar, 3. Aufl. 2012, N. 7 zu Art. 50 AuG). Dabei ist Art. 50 Abs. 1 lit. b AuG im Licht der verfassungs- und konventionsrechtlichen Garantien zum Schutz des Familienlebens (<ref-law>; Art. 8 Ziff. 1 EMRK) auszulegen (Urteile 2C_336/2012 vom 3. August 2012 E. 2.2; 2C_578/2011 vom 1. Dezember 2011 E. 3.4.1).
Nach der Rechtsprechung setzt ein persönlicher, nachehelicher Härtefall aufgrund der gesamten Umstände des Einzelfalls eine erhebliche Intensität der Konsequenzen für das Privat- und Familienleben voraus, die mit der Lebenssituation nach dem Dahinfallen der abgeleiteten Anwesenheitsberechtigung verbunden sind (<ref-ruling> E. 3.1 am Ende S. 332). Geht es um die Kontaktpflege mit einem in der Schweiz lebenden Kind, wird dem nicht obhutsberechtigten ausländischen Elternteil die Aufenthaltsbewilligung im Rahmen von Art. 50 Abs. 1 lit. b AuG nur ausnahmsweise verlängert, denn er kann die familiäre Beziehung zu seinem Kind aus zivilrechtlichen Gründen ohnehin nur eingeschränkt, durch Ausübung des ihm eingeräumten Besuchsrechts, leben (Urteile 2C_336/2012 vom 3. August 2012 E. 3.2; 2C_578/2011 vom 1. Dezember 2011 E. 3.4.3 mit Hinweisen). Praxisgemäss erscheint die Verlängerung der Aufenthaltsbewilligung des nicht obhutsberechtigten ausländischen Elternteils nur geboten, wenn dieser mit dem Kind eine wirtschaftlich und affektiv besonders enge Beziehung pflegt (<ref-ruling> E. 3c S. 5), die wegen der Distanz zum Herkunftsland praktisch nicht aufrechterhalten werden könnte (<ref-ruling> E. 4a S. 24 f.; Urteil des EGMR Rodrigues da Silva und Hoogkamer gegen Niederlande vom 31. Januar 2006 [50435/99], § 42). Zudem wird in diesem Zusammenhang verlangt, dass die ausländische Person bisher zu keinen Klagen Anlass gegeben hat (Urteile 2C_769/2012 vom 22. Oktober 2012 E. 3.4; 2C_272/2008 vom 15. Januar 2009 E. 2.2).
4. 4.1 Das Zivilgericht des Kantons Basel-Stadt verpflichtete den Beschwerdeführer am 4. Dezember 2009 zur Bezahlung von monatlichen Unterhaltsbeiträgen in der Höhe von Fr. 270.-- an seine Tochter Z._. Dieser Betrag wurde aufgrund des bescheidenen Einkommens des Beschwerdeführers von damals monatlich knapp Fr. 3'000.-- brutto festgesetzt, wobei das Gericht anordnete, dass die Beiträge jeweils direkt vom Lohn des Beschwerdeführers abzuziehen und via Sozialhilfe der Stadt Basel der Ehefrau gutzuschreiben seien (Dispositiv Ziff. 5 der Verfügung des Zivilgerichts Basel-Stadt vom 4. Dezember 2009). Der Beschwerdeführer selbst gab gegenüber dem Bundesamt für Migration am 18. März 2010 an, er leiste Alimente in der Höhe von Fr. 270.-- monatlich; verdiene er über Fr. 2'900.--, gebe er auch diesen Betrag ab. Die Feststellung der Vorinstanz, wonach der Beschwerdeführer den Betrag von Fr. 270.-- nicht regelmässig geleistet habe (vgl. E. 7.3 des angefochtenen Urteils), erweist sich somit als offensichtlich unrichtig. In Anwendung von <ref-law> ist davon auszugehen, dass die gerichtlich festgesetzten Unterhaltsbeiträge von Fr. 270.-- durch die Arbeitgeberin des Beschwerdeführers regelmässig an dessen Ehefrau überwiesen wurden.
Der Beschwerdeführer leistete demnach im Rahmen seiner finanziellen Möglichkeiten ab Dezember 2009 bescheidene Unterhaltsbeiträge an seine Tochter. Gemäss Arbeitsvertrag vom 22. Dezember 2010 verdiente er ab Januar 2011 Fr. 3'800.-- brutto und gemäss Arbeitsvertrag vom 22. Juni 2011 seit dem 1. Juni 2011 rund Fr. 4'000.-- brutto pro Monat. Sein Vorbringen, er würde das gesamte überschüssige Einkommen seiner Familie zukommen lassen, belegt der Beschwerdeführer jedoch nicht. Die Angabe seiner Ehefrau, wonach er sie "ohne Wenn und Aber" finanziell unterstütze, kann nicht als Beweis für den behaupteten Sachverhalt gelten. Die Vorinstanz hat daher die wirtschaftliche Abhängigkeit der Tochter vom Beschwerdeführer im Ergebnis zu Recht als gering eingestuft. Auch wenn aus dem Verhandlungsprotokoll des Zivilgerichts des Kantons Basel-Stadt vom 13. Februar 2012 hervorgeht, dass die Unterhaltsbeiträge anlässlich der Scheidung neu festgesetzt würden, ändert dies nichts an den geleisteten Beiträgen von monatlich Fr. 270.-- im massgeblichen Zeitraum von Dezember 2009 bis zum Erlass des angefochtenen Urteils. Von einer besonderen wirtschaftlichen Abhängigkeit des Kindes kann daher nicht gesprochen werden.
4.2 Hinsichtlich der Beziehung des Beschwerdeführers zu seiner Tochter ist vorab festzuhalten, dass dieser nur knapp achteinhalb Monate (vom 13. Januar 2008 bis zum 25. April 2008 und vom 1. Mai 2009 bis zum 30. September 2009) mit ihr zusammengelebt hat. Seither pflegt er den Kontakt zu seiner Tochter im Rahmen der mit der Ehefrau vereinbarten Besuchs- und Ferienregelung.
Gemäss den Erwägungen der Vorinstanz deuten verschiedene Sachverhaltselemente darauf hin, dass die Hauptlast der Betreuungsaufgaben bei der Ehefrau liegt. So habe der Beschwerdeführer nur vage Angaben zur Ausgestaltung des Besuchsrechts gemacht und dies auch erst, nachdem er auf seine Mitwirkungspflichten hingewiesen worden sei. Die Vorinstanz konnte trotz ausdrücklicher Aufforderung an den Beschwerdeführer, seine familiäre Situation bzw. das Besuchsrecht darzulegen, nicht zweifelsfrei feststellen, wie oft und wie lange jeweils der Beschwerdeführer seine Tochter sieht. Sie kam zum Schluss, dies sei wohl an den Wochenenden der Fall, wobei die Tochter nicht beim Beschwerdeführer übernachte, weil dessen Wohnung dafür nicht geeignet sei. Zudem springe er während der Woche gelegentlich am Abend ein, wenn die Ehefrau länger arbeiten müsse. Auch wenn der Beschwerdeführer seine Tochter jedes Wochenende treffen sollte, könne davon ausgegangen werden, dass er sie nur einige Stunden und nicht ein ganzes Wochenende betreue. Gegen eine Betreuung des Kindes während der Woche spreche die Tatsache, dass die Ehefrau mit Schreiben vom 7. Mai 2010 angegeben habe, sie werde eine Arbeitsstelle antreten, sobald sie für ihre Tochter einen Platz in einem Tagesheim gefunden habe. Von einer grosszügigen Ausgestaltung des Besuchsrechts - Zeichen für eine besonders intensive affektive Beziehung - könne bei dieser Sachlage nicht die Rede sein.
Diesen Ausführungen ist beizupflichten. Der Beschwerdeführer legt nicht dar, inwiefern die Sachverhaltsfeststellung der Vorinstanz hinsichtlich der Häufigkeit und Intensität seiner Kontakte zum Kind willkürlich wäre. Zu Recht hat die Vorinstanz aus den Stellungnahmen des Beschwerdeführers vom 1. März 2012 und seiner Frau vom 28. Februar 2012 betreffend die Ausgestaltung des Besuchsrechts, in denen jeweils von "vereinbarten Wochenenden und Tagen" die Rede ist, nicht auf eine regelmässige, institutionalisierte Betreuung geschlossen, welche über das dem nicht obhut- und sorgeberechtigten Partner gewöhnlich eingeräumte Besuchsrecht hinausginge. Es ist somit nicht willkürlich, wenn die Vorinstanz eine besonders enge affektive Beziehung des Beschwerdeführers zu seiner Tochter verneint hat.
Für die Wahrung des legitimen Interesses des Beschwerdeführers, den Kontakt zu seiner Tochter aufrecht zu erhalten, ist seine dauernde Anwesenheit in der Schweiz rechtsprechungsgemäss (vgl. E. 3.3 hiervor) nicht erforderlich. Den Anforderungen an Art. 8 Ziff. 1 EMRK ist Genüge getan, wenn das Besuchsrecht im Rahmen von Kurzaufenthalten vom Ausland her ausgeübt werden kann, wobei allenfalls dessen Modalitäten entsprechend auszugestalten sind (vgl. Urteil 2C_272/2008 vom 15. Januar 2009 E. 2.2).
4.3 Während seiner Anwesenheit in der Schweiz hat der Beschwerdeführer in verschiedener Hinsicht Anlass zu Klagen gegeben:
4.3.1 Nach der rechtskräftigen Abweisung seines Asylgesuchs bzw. nach Ablauf der Ausreisefrist am 13. Mai 2002 hielt sich der Beschwerdeführer bis zu seiner Heirat am 3. März 2006, somit ungefähr drei Jahre und zehn Monate ohne Aufenthaltsstatus, d.h. illegal in der Schweiz auf. Die Duldung einer Person ohne Aufenthaltsrecht durch die Behörden macht den Aufenthalt nicht rechtmässig (Urteil 2C_56/2012 vom 24. September 2012 E. 5.2).
4.3.2 Die Schulden des Beschwerdeführers (Betreibungen und Verlustscheine) beliefen sich am 28. Februar 2012 (Datum des Betreibungsregisterauszugs) auf über Fr. 44'000.--.
4.3.3 Zwischen dem 1. September 2006 und 31. August 2009 bezog der Beschwerdeführer Sozialhilfe in der Höhe von insgesamt rund Fr. 33'000.--. Zwischen Februar 2011 und Februar 2012 leistete er monatliche Rückzahlungen von Fr. 40.-- bis Fr. 50.-- an die Sozialhilfe der Stadt Basel.
4.3.4 Die Vorinstanz hat diese Umstände im Rahmen von Art. 96 Abs. 1 AuG zuungunsten des Beschwerdeführers gewürdigt. Dies ist nicht zu beanstanden, vermögen doch die Rückzahlungen an die Sozialhilfe das rechtswidrige Verhalten des Beschwerdeführers, namentlich den illegalen Aufenthalt und die Anhäufung von Schulden, nicht aufzuwiegen.
4.4 Die Gesamtwürdigung der Umstände zeigt, dass ein nachehelicher Härtefall im Sinn von Art. 50 Abs. 1 lit. b AuG zu verneinen ist. Die räumliche Trennung von der Tochter bewirkt keine derart einschneidende Veränderung im Leben des Beschwerdeführers, dass seine dauerhafte Anwesenheit in der Schweiz erforderlich wäre. Die Nichtverlängerung der Aufenthaltsbewilligung ist mit Art. 8 Ziff. 1 EMRK vereinbar. Der Beschwerdeführer wird die Beziehung zu seiner Tochter - wenn auch mit Einschränkungen - aus dem Ausland pflegen können. Im Übrigen sind keine Umstände ersichtlich, welche eine Rückkehr des Beschwerdeführers in seine Heimat als unzumutbar erscheinen liessen; solche werden auch nicht geltend gemacht.
5. Aus dem Gesagten ergibt sich, dass die Beschwerde als unbegründet abzuweisen ist, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens sind dem Beschwerdeführer die Gerichtskosten aufzuerlegen (<ref-law>); Anspruch auf eine Parteientschädigung besteht nicht (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 1'500.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten und dem Bundesverwaltungsgericht, Abteilung III, schriftlich mitgeteilt.
Lausanne, 16. Dezember 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Genner