Sachverhalt: A. X._ wurde 1976 im Irak geboren und lebte nach eigenen Angaben von 1978 bis 1999 im Libanon. Am 5. April 1999 gelangte er in die Schweiz und ersuchte um Asyl. Das Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) lehnte mit Verfügung vom 20. Februar 2000 sein Asylgesuch ab und die damals zuständige Asylrekurskommission (heute: Bundesverwaltungsgericht) bestätigte am 20. September 2000 diesen Entscheid. Mit Verfügung vom 16. Mai 2001 erteilte die Migrationsbehörde des Kantons Schaffhausen X._ eine Jahresaufenthaltsbewilligung, da er beim zuständigen Zivilstandesamt den Schweizer Bürger Y._ (geb. 2000) als sein Kind anerkannt hatte. B. Im Zusammenhang mit einem noch hängigen Gesuch um Ausstellung eines Passes für eine ausländische Person gelangte X._ am 17. Februar 2006 an das Bundesamt für Migration und beantragte formell die Anerkennung seiner Staatenlosigkeit. Er brachte vor, obwohl im Irak geboren, habe er nie über einen entsprechenden Ausweis verfügt. Auch im Libanon sei er nie als Staatsangehöriger aufgenommen worden. Das Bundesamt für Migration lehnte mit Verfügung vom 3. April 2006 das Gesuch um Anerkennung der Staatenlosigkeit ab. Es machte unter anderem geltend, als Sohn eines Irakers sei er von Gesetzes wegen irakischer Staatsangehöriger und somit nicht staatenlos. In der Folge wandte sich X._ am 20. April 2006 mit einem Wiedererwägungsgesuch an das Bundesamt für Migration, welches die Eingabe an das damals zuständige Eidgenössische Justiz- und Polizeidepartement (EJPD) überwies; dieses nahm die Eingabe als Beschwerde entgegen. Am 1. Januar 2007 übernahm das Bundesverwaltungsgericht die Beurteilung des beim Beschwerdedienst des EJPD hängigen Rechtsmittels und wies mit Urteil vom 9. September 2008 die Beschwerde ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 19. Oktober 2008 beantragt X._ dem Bundesgericht, den Entscheid des Bundesverwaltungsgerichts aufzuheben sowie festzustellen, dass der Beschwerdeführer staatenlos sei. Sodann ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. Gerügt wird im Wesentlichen, die Vorinstanz habe "klare Auslegungsfehler" begangen. Sinngemäss wird eine Verletzung der völkerrechtlichen Bestimmungen über die Staatenlosigkeit geltend gemacht. D. Das Bundesamt für Migration beantragt die Abweisung der Beschwerde. Das Bundesverwaltungsgericht hat auf eine Vernehmlassung verzichtet. 