Sachverhalt: A. A.a X._, geboren 1993, reiste gemäss eigenen Angaben am 1. Januar 2012 illegal in die Schweiz ein und stellte am 2. Januar 2012 ein Asylgesuch. Am 27. März 2012 wies das Bundesamt für Migration (BFM) das Gesuch wegen fehlender Flüchtlingseigenschaft ab und ordnete unter Androhung von Zwangsmitteln im Unterlassungsfall an, X._ habe die Schweiz bis am 22. Mai 2012 zu verlassen. Der Kanton Aargau wurde mit dem Vollzug der Wegweisung beauftragt. A.b X._ kam der Ausreiseverpflichtung nicht nach. Das Amt für Migration und Integration des Kantons Aargau (nachfolgend: Migrationsamt) wies ihn wiederholt auf seine Pflicht hin, bei der Beschaffung von Reisepapieren mitzuwirken. Am 20. Juni 2012 gab X._ an, guineischer Staatsbürger zu sein und nicht nach Guinea ausreisen zu wollen. Ein Herkunftsspezialist stellte am 17. Juli 2012 fest, X._ spreche Wolof mit einem Akzent, wie er in Gambia gesprochen werde, und bestätigte, dieser habe zweifellos sein ganzes Leben in Gambia verbracht. A.c Am 6. August 2012 wurde X._ von der Kantonspolizei Aargau festgenommen. Er erklärte sich weder bereit, nach Guinea noch nach Gambia auszureisen. Das Migrationsamt gewährte X._ das rechtliche Gehör und eröffnete ihm sodann die Anordnung der Ausschaffungshaft für drei Monate. B. X._ focht die Haftanordnung beim damaligen Rekursgericht im Ausländerrecht des Kantons Aargau (heute: Verwaltungsgericht des Kantons Aargau; nachfolgend: Verwaltungsgericht) erfolgreich an. Mit Urteil vom 7. August 2012 entschied das Verwaltungsgericht, die am 6. August 2012 durch das Migrationsamt angeordnete Ausschaffungshaft werde nicht bestätigt und X._ sei unverzüglich aus der Ausschaffungshaft zu entlassen. C. Gegen diesen Entscheid erhob das BFM am 28. September 2012 Beschwerde beim Bundesgericht mit dem Antrag, das Urteil des Verwaltungsgerichts vom 7. August 2012 sei aufzuheben. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde, ebenso X._. Das Migrationsamt schliesst auf Gutheissung der Beschwerde. 