Sachverhalt: A. Der nigerianische Staatsangehörige X._, geb. 1988, reiste im Juli 2008 illegal in die Schweiz ein und stellte hier ein Asylgesuch. Das Bundesamt für Migration trat auf sein Gesuch nicht ein und wies ihn aus der Schweiz weg. X._ erhob dagegen Beschwerde beim Bundesverwaltungsgericht. Mit Strafmandat vom 29. Mai 2009 wurde X._ wegen rechtswidrigen Aufenthalts und Verstosses gegen das Betäubungsmittelgesetz zu einer bedingt vollziehbaren Geldstrafe von 60 Tagessätzen zu Fr. 20.-- verurteilt. Der Beziehung mit einer Schweizerbürgerin entsprang am 4. November 2009 ein gemeinsamer Sohn. X._ stellte daraufhin ein Gesuch um Erteilung einer Aufenthaltsbewilligung. Das Amt für Migration und Personenstand des Kantons Bern wies das Gesuch am 14. April 2011 ab. Am 3. Mai 2011 wies das Bundesverwaltungsgericht die Beschwerde gegen den Asylentscheid ab, hob jedoch wegen des hängigen ausländerrechtlichen Verfahrens die vom Bundesamt für Migration angeordnete Wegweisung auf. B. Gegen die Verfügung des Amtes für Migration und Personenstand des Kantons Bern erhob X._ erfolglos Beschwerde an die Polizei- und Militärdirektion des Kantons Bern und anschliessend an das Verwaltungsgericht des Kantons Bern. Dieses wies mit Urteil vom 21. März 2012 die Beschwerde ab und setzte dem Beschwerdeführer eine Ausreisefrist bis 3. Mai 2012. C. X._ erhebt Beschwerde in öffentlich-rechtlichen Angelegenheiten, eventualiter subsidiäre Verfassungsbeschwerde, mit dem Antrag, es sei ihm eine Aufenthaltsbewilligung zu erteilen, eventuell die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Er beantragt weiter, der Beschwerde sei die aufschiebende Wirkung zuzuerkennen und es sei ihm das Recht zur unentgeltlichen Rechtspflege zu erteilen. D. Mit Verfügung vom 4. Mai 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt. Das Verwaltungsgericht des Kantons Bern, die Polizei- und Militärdirektion des Kantons Bern und das Bundesamt für Migration beantragen die Abweisung der Beschwerde. Mit Eingabe vom 16. August 2012 hält der Beschwerdeführer an seinem Begehren fest.