Sachverhalt: A. Der aus Mali stammende A._ (geb. 1973) ersuchte am 31. Oktober 2001 in der Schweiz unter falscher Identität (B._, geb. 1972, Guinea) um Asyl. Das Bundesamt für Flüchtlinge wies sein Gesuch am 30. September 2002 ab. Mit Urteil vom 27. November 2002 bestätigte die Schweizerische Asylrekurskommission diesen Entscheid. In der Folge galt A._ (alias B._) als verschwunden. B. Am 10. September 2003 wurde A._ in Biel angehalten und tags darauf in Ausschaffungshaft genommen. Bei seiner Einvernahme gab er an, die Schweiz nach dem Asylverfahren verlassen zu haben, um sich in seiner Heimat die für die Heirat mit der Schweizer Bürgerin C._ (geb. 1954) nötigen Papiere zu beschaffen. Seit eineinhalb Jahren habe er bei seiner Verlobten gelebt. Am 22. April 2003 sei er in die Schweiz zurückgekehrt; am 23. April 2003 habe er beim Zivilstandsamt Biel-Nidau das Ehevorbereitungsverfahren eingeleitet, wobei sein Rechtsvertreter am gleichen Tag das Migrationsamt des Kantons Bern um Erteilung einer Aufenthaltsbewilligung zwecks Vorbereitung der Heirat ersucht habe. Das Haftgericht III Bern-Mittelland prüfte und bestätigte die Ausschaffungshaft am 12. September 2003. Mit Entscheid vom 9. Dezember 2003 genehmigte es eine Haftverlängerung bis zum 9. April 2004. C. A._ hat hiergegen am 16. Dezember 2003 beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht mit dem Antrag, ihn aus der Haft zu entlassen und ihm bis zur Heirat eine vorläufige Aufenthaltsbewilligung zu erteilen. Das Haftgericht III Bern-Mittelland und die Fremdenpolizei der Stadt Biel beantragen, die Beschwerde abzuweisen. A._ hat von der Möglichkeit, zu den Vernehmlassungen Stellung zu nehmen, keinen Gebrauch gemacht. D. Mit Verfügung vom 12. Januar 2004 forderte der Abteilungspräsident das Eidgenössische Justiz- und Polizeidepartement (Abteilung Vollzugsunterstützung) auf, einen Amtsbericht bezüglich der Möglichkeiten eines zwangsweisen Vollzugs von Wegweisungen nach Mali zu erstatten, was es am 15./16. Januar 2004 getan hat. 