Sachverhalt: A. X._, geboren 1966, ist Staatsangehöriger der Demokratischen Republik Kongo. Im März 2001 reiste er in die Schweiz ein. Sein Asylgesuch, das er hier stellte, wies das damalige Bundesamt für Flüchtlinge im folgenden Monat ab und ordnete die Wegweisung aus der Schweiz an. X._ erhob Beschwerde an die seinerzeitige Schweizerische Asylrekurskommission. Er zog diese zurück, nachdem er im November 2002 eine Schweizerbürgerin, geboren 1959, geheiratet und vom Kanton Basel-Stadt eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau erhalten hatte. Nach einer Ehedauer von rund 13 Monaten gaben die Eheleute den gemeinsamen Haushalt im Dezember 2003 auf. Die Ehe wurde im Oktober 2006 geschieden. B. Bald nach Aufhebung des gemeinsamen Haushaltes zog X._ bei einer Schweizerbürgerin ein, die 1956 geboren wurde. Im Hinblick auf die Scheidung und die beabsichtigte Verheiratung mit der Freundin wurde die Aufenthaltsbewilligung mehrfach verlängert (letztmals bis zum 20. November 2008). Die Freundin kam später auf ihre Absicht zurück und trennte sich von X._. Der Beziehung mit einer weiteren Schweizerbürgerin, geboren 1963, entsprang im August 2005 eine Tochter. X._ und die Kindsmutter hatten vor, die Ehe einzugehen. Zum Eheschluss kam es freilich nicht, ebenso wenig wie X._ in gemeinsamem Haushalt mit der Kindsmutter und seiner Tochter lebt. Aufgrund einer Vereinbarung vom Oktober 2005 schuldet der Kindsvater gegenüber seiner Tochter Unterhaltsbeiträge von Fr. 300.-- pro Monat. Aus der Unterhaltsvereinbarung geht kein verbindliches Besuchsrecht hervor. Auf einvernehmlicher Basis übt X._ ein solches jeweils an Sonntagen in Anwesenheit der Kindsmutter aus. C. Aus anderen Beziehungen in seiner Heimat ist X._ Vater vier weiterer Kinder. Während langer Zeit war er in der Schweiz von der Sozialhilfe abhängig und bezog allein bis Ende März 2009 rund Fr. 65'000.--. Seit März 2011 ist er in einer Unternehmung angestellt, die Sozialhilfeempfänger beschäftigt. X._ leidet an einer Infektion mit dem humanen Immundefizienz-Virus (HIV). Die Krankheit hat das Stadium B erreicht. Aufgrund der antiretroviralen Therapie befindet X._ sich in gutem und stabilem medizinischem Allgemeinzustand. D. Am 11. Dezember 2008 unterbreitete die Migrationsbehörde des Kantons Basel-Stadt dem Bundesamt für Migration das Gesuch zur erneuten Verlängerung der Aufenthaltsbewilligung. Mit Verfügung vom 9. Februar 2009 verweigerte das Bundesamt seine Zustimmung. Dagegen gelangte X._ am 12. März 2009 an das Bundesverwaltungsgericht, das die Beschwerde mit Urteil vom 3. April 2012 abwies, soweit darauf einzutreten war. E. Mit Eingabe vom 7. Mai 2012 an das Bundesgericht erhebt X._ (hiernach: der Beschwerdeführer) Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt, das angefochtene Urteil vom 3. April 2012 sei aufzuheben und es sei die Zustimmung zur Verlängerung der Aufenthaltsbewilligung zu erteilen, eventualiter sei der Fall zur Neubeurteilung an die Vorinstanz zurückzuweisen. Er beantragt weiter, es sei ihm das Recht zur unentgeltlichen Rechtspflege zu erteilen, der Beschwerde sei die aufschiebende Wirkung zuzuerkennen und die Tochter sei "angemessen anzuhören". Während die Vorinstanz auf eine Vernehmlassung verzichtet, beantragt das Bundesamt für Migration die Abweisung der Beschwerde. Mit Verfügung vom 11. Mai 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.