Sachverhalt:
Sachverhalt:
A. Der am ... 1978 geborene, aus Bangladesh stammende X._ reiste gemäss eigenen Angaben am 15. Juni 1998 von Italien her kommend in die Schweiz ein und stellte gleichentags unter dem Aliasnamen Y._ ein Asylgesuch. Mit Verfügung vom 13. November 1998 lehnte das Bundesamt für Flüchtlinge das Asylgesuch ab und wies Y._ aus der Schweiz weg. Mit Urteil vom 15. Januar 1999 trat die Schweizerische Asylrekurskommission auf die dagegen erhobene Beschwerde nicht ein. X._ alias Y._ reiste in der Folge nicht aus der Schweiz aus. Am 20. März 2001 teilte das Amt für öffentliche Sicherheit des Kantons Solothurn dem Bundesamt für Flüchtlinge mit, Y._ gelte seit dem 9. März 2001 als verschwunden.
A. Der am ... 1978 geborene, aus Bangladesh stammende X._ reiste gemäss eigenen Angaben am 15. Juni 1998 von Italien her kommend in die Schweiz ein und stellte gleichentags unter dem Aliasnamen Y._ ein Asylgesuch. Mit Verfügung vom 13. November 1998 lehnte das Bundesamt für Flüchtlinge das Asylgesuch ab und wies Y._ aus der Schweiz weg. Mit Urteil vom 15. Januar 1999 trat die Schweizerische Asylrekurskommission auf die dagegen erhobene Beschwerde nicht ein. X._ alias Y._ reiste in der Folge nicht aus der Schweiz aus. Am 20. März 2001 teilte das Amt für öffentliche Sicherheit des Kantons Solothurn dem Bundesamt für Flüchtlinge mit, Y._ gelte seit dem 9. März 2001 als verschwunden.
B. Am 5. Februar 2002 nahm die Kantonspolizei Basel-Stadt X._ alias Y._ in Basel fest. Am 6. Februar 2002 nahm ihn das Amt für öffentliche Sicherheit des Kantons Solothurn in Ausschaffungshaft. Mit Urteil vom 8. Februar 2002 prüfte und genehmigte der Vizepräsident des Verwaltungsgerichts des Kantons Solothurn als Haftrichter die Ausschaffungshaft bis zum 5. Mai 2002. Mit Schreiben vom 20. März 2002 ersuchte X._ alias Y._ um Entlassung aus der Ausschaffungshaft; er räumte ein, dass er bisher unter einem falschen Namen aufgetreten sei und legte Kopien von Identitätspapieren vor; mit Schreiben vom 21. März 2002 sandte er die entsprechenden Originale nach. Er teilte zudem mit, er habe vor, seine über die Niederlassungsbewilligung verfügende Freundin Z._ in Bangladesh zu heiraten und im Anschluss daran ein ordentliches Familiennachzugsgesuch zu stellen. Mit Urteil vom 3. April 2002 wies der Vizepräsident des Verwaltungsgerichts das Haftentlassungsgesuch ab. Am 3. Mai 2002 genehmigte der Präsident des Verwaltungsgerichts eine Haftverlängerung bis zum 5. August 2002. Am 26. Juni 2002 wies der Vizepräsident des Verwaltungsgerichts ein weiteres Haftentlassungsgesuch ab. Am 31. Juli 2002 entliess das Amt für öffentliche Sicherheit, Ausländerfragen, X._ aus der Ausschaffungshaft, hielt ihn aber dazu an, sich alle zwei Wochen im Asylbüro zu melden.
B. Am 5. Februar 2002 nahm die Kantonspolizei Basel-Stadt X._ alias Y._ in Basel fest. Am 6. Februar 2002 nahm ihn das Amt für öffentliche Sicherheit des Kantons Solothurn in Ausschaffungshaft. Mit Urteil vom 8. Februar 2002 prüfte und genehmigte der Vizepräsident des Verwaltungsgerichts des Kantons Solothurn als Haftrichter die Ausschaffungshaft bis zum 5. Mai 2002. Mit Schreiben vom 20. März 2002 ersuchte X._ alias Y._ um Entlassung aus der Ausschaffungshaft; er räumte ein, dass er bisher unter einem falschen Namen aufgetreten sei und legte Kopien von Identitätspapieren vor; mit Schreiben vom 21. März 2002 sandte er die entsprechenden Originale nach. Er teilte zudem mit, er habe vor, seine über die Niederlassungsbewilligung verfügende Freundin Z._ in Bangladesh zu heiraten und im Anschluss daran ein ordentliches Familiennachzugsgesuch zu stellen. Mit Urteil vom 3. April 2002 wies der Vizepräsident des Verwaltungsgerichts das Haftentlassungsgesuch ab. Am 3. Mai 2002 genehmigte der Präsident des Verwaltungsgerichts eine Haftverlängerung bis zum 5. August 2002. Am 26. Juni 2002 wies der Vizepräsident des Verwaltungsgerichts ein weiteres Haftentlassungsgesuch ab. Am 31. Juli 2002 entliess das Amt für öffentliche Sicherheit, Ausländerfragen, X._ aus der Ausschaffungshaft, hielt ihn aber dazu an, sich alle zwei Wochen im Asylbüro zu melden.
C. Am 8. Januar 2004 übermittelte das Eidgenössische Justiz- und Polizeidepartement dem Amt für öffentliche Sicherheit des Kantons Solothurn eine Kopie der Geburtsurkunde von X._, eine Kopie des so genannten "National Certificate", beglaubigt im August 2003, eine Kopie seines am 16. Oktober 2003 ausgestellten Passes und eine Bestätigung seiner Mutter, wonach er noch ledig sei. Diese stammten von der schweizerischen Vertretung in Dhaka, welche die betreffenden Dokumente im Hinblick auf die geplante Eheschliessung überprüft hatte.
C. Am 8. Januar 2004 übermittelte das Eidgenössische Justiz- und Polizeidepartement dem Amt für öffentliche Sicherheit des Kantons Solothurn eine Kopie der Geburtsurkunde von X._, eine Kopie des so genannten "National Certificate", beglaubigt im August 2003, eine Kopie seines am 16. Oktober 2003 ausgestellten Passes und eine Bestätigung seiner Mutter, wonach er noch ledig sei. Diese stammten von der schweizerischen Vertretung in Dhaka, welche die betreffenden Dokumente im Hinblick auf die geplante Eheschliessung überprüft hatte.
D. Am 9. Januar 2004 befragte das Amt für öffentliche Sicherheit, Ausländerfragen, des Kantons Solothurn X._, konfrontierte ihn mit den Kopien des Passes und des National Certificate und eröffnete ihm, dass es ihn wiederum in Ausschaffungshaft nahmen werde. Hierauf forderte Z._ ihren Freund auf, mit ihr das Büro zu verlassen, worauf dieser davonlief. Als der befragende Beamte die Verfolgung aufnehmen wollte, stellte sich Z._ ihm in den Weg, worauf X._ entkam.
Am 18. März 2004 nahm die Kantonspolizei Basel-Stadt X._ in der Wohnung seiner Freundin Z._ fest; tags darauf nahm ihn das Amt für öffentliche Sicherheit, Ausländerfragen, des Kantons Solothurn in Ausschaffungshaft. Mit Urteil vom 22. März 2004 prüfte und genehmigte der Präsident des Verwaltungsgerichts des Kantons Solothurn die Ausschaffungshaft bis zum 17. Mai 2004.
Am 18. März 2004 nahm die Kantonspolizei Basel-Stadt X._ in der Wohnung seiner Freundin Z._ fest; tags darauf nahm ihn das Amt für öffentliche Sicherheit, Ausländerfragen, des Kantons Solothurn in Ausschaffungshaft. Mit Urteil vom 22. März 2004 prüfte und genehmigte der Präsident des Verwaltungsgerichts des Kantons Solothurn die Ausschaffungshaft bis zum 17. Mai 2004.
E. Dagegen hat X._ am 25. März 2004 beim Bundesgericht Verwaltungsgerichtsbeschwerde erhoben. Er beantragt, das Urteil des Verwaltungsgerichts aufzuheben und ihn aus der Haft zu entlassen. Zudem ersucht er um unentgeltliche Rechtspflege und Verbeiständung.
Das Departement des Innern, Abteilung Ausländerfragen, sowie das Verwaltungsgericht des Kantons Solothurn beantragen, die Beschwerde abzuweisen. Das Bundesamt für Flüchtlinge hat sich nicht vernehmen lassen. Mit Schreiben vom 1. April 2004 hält X._ am Antrag auf Haftentlassung fest.
Das Departement des Innern, Abteilung Ausländerfragen, sowie das Verwaltungsgericht des Kantons Solothurn beantragen, die Beschwerde abzuweisen. Das Bundesamt für Flüchtlinge hat sich nicht vernehmen lassen. Mit Schreiben vom 1. April 2004 hält X._ am Antrag auf Haftentlassung fest.
F. Mit Schreiben vom 25. März 2004 ersuchte X._ das Bundesamt für Flüchtlinge um Wiedererwägung seiner Wegweisungsverfügung vom 13. November 1998.
F. Mit Schreiben vom 25. März 2004 ersuchte X._ das Bundesamt für Flüchtlinge um Wiedererwägung seiner Wegweisungsverfügung vom 13. November 1998.
G. Mit Verfügung vom 26. März 2004 hat der Abteilungspräsident das Gesuch um sofortige Haftentlassung bzw. um aufschiebende Wirkung zur Zeit abgewiesen.

Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. 1.1 Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen, sofern die Voraussetzungen von Art. 13b ANAG erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2 S. 61; <ref-ruling> E. 3a S. 374; <ref-ruling> E. 1 S. 150), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist (BGE <ref-ruling> E. 3a S. 374, 377 E. 2a S. 379). Sodann muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (BGE <ref-ruling> E. 3a S. 374, 377 E. 3a S. 381; <ref-ruling> E. 1 S. 3) und die Ausschaffung rechtlich und tatsächlich möglich sein (vgl. Art. 13c Abs. 5 lit. a ANAG; dazu <ref-ruling> E. 2 S. 220, 377 E. 5 S. 384). Auf Seiten der Behörden sind die für den Vollzug der Wegweisung notwendigen Vorkehrungen (wie Identitäts- und Herkunftsabklärungen, Papierbeschaffung) umgehend zu treffen (Art. 13b Abs. 3 ANAG, Beschleunigungsgebot; vgl. <ref-ruling> ff.).
1. 1.1 Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen, sofern die Voraussetzungen von Art. 13b ANAG erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2 S. 61; <ref-ruling> E. 3a S. 374; <ref-ruling> E. 1 S. 150), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist (BGE <ref-ruling> E. 3a S. 374, 377 E. 2a S. 379). Sodann muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (BGE <ref-ruling> E. 3a S. 374, 377 E. 3a S. 381; <ref-ruling> E. 1 S. 3) und die Ausschaffung rechtlich und tatsächlich möglich sein (vgl. Art. 13c Abs. 5 lit. a ANAG; dazu <ref-ruling> E. 2 S. 220, 377 E. 5 S. 384). Auf Seiten der Behörden sind die für den Vollzug der Wegweisung notwendigen Vorkehrungen (wie Identitäts- und Herkunftsabklärungen, Papierbeschaffung) umgehend zu treffen (Art. 13b Abs. 3 ANAG, Beschleunigungsgebot; vgl. <ref-ruling> ff.).
2. 2.1 Der Beschwerdeführer ist im Asylverfahren rechtskräftig weggewiesen worden. Die Ausschaffungshaft ist zum Vollzug dieser Wegweisung angeordnet worden.
2.2 Der Haftgrund der Untertauchensgefahr (Art. 13b Abs. 1 lit. c ANAG) ist gegeben, ist doch der Beschwerdeführer bei seiner Einreise in die Schweiz im Jahre 1998 bis im März 2002 unter einem falschen Namen aufgetreten; dazu kommt, dass er vom 9. März 2001 bis zum 5. Februar 2002 untergetaucht war; wie sich später herausstellte, wurde er während dieser Zeit von seiner Freundin beherbergt. Auch mit der Preisgabe seiner Identität am 20. März 2002 ist die Untertauchensgefahr nicht entfallen: Der Beschwerdeführer hat den Ausländerbehörden verschwiegen, dass er seit dem Herbst 2003 über einen Reisepass verfügt; dazu kommt, dass er anlässlich der Befragung vom 9. Januar 2004 die Flucht ergriff, um sich der Ausschaffungshaft zu entziehen. Damit bietet er keine Gewähr dafür, dass er sich zu gegebener Zeit für die Ausschaffung zur Verfügung halten wird.
2.2 Der Haftgrund der Untertauchensgefahr (Art. 13b Abs. 1 lit. c ANAG) ist gegeben, ist doch der Beschwerdeführer bei seiner Einreise in die Schweiz im Jahre 1998 bis im März 2002 unter einem falschen Namen aufgetreten; dazu kommt, dass er vom 9. März 2001 bis zum 5. Februar 2002 untergetaucht war; wie sich später herausstellte, wurde er während dieser Zeit von seiner Freundin beherbergt. Auch mit der Preisgabe seiner Identität am 20. März 2002 ist die Untertauchensgefahr nicht entfallen: Der Beschwerdeführer hat den Ausländerbehörden verschwiegen, dass er seit dem Herbst 2003 über einen Reisepass verfügt; dazu kommt, dass er anlässlich der Befragung vom 9. Januar 2004 die Flucht ergriff, um sich der Ausschaffungshaft zu entziehen. Damit bietet er keine Gewähr dafür, dass er sich zu gegebener Zeit für die Ausschaffung zur Verfügung halten wird.
3. 3.1 Der Beschwerdeführer macht geltend, der Vollzug der Wegweisung sei derzeit aus rechtlichen Gründen im Sinne von Art. 13c Abs. 5 lit. a ANAG nicht durchführbar. Die Wegweisung als solche hingegen ficht er nicht im vorliegenden Haftprüfungsverfahren an, sondern in Form eines Wiedererwägungsgesuchs beim Bundesamt für Flüchtlinge; dies zu Recht, denn die Frage, ob eine Wegweisung wegen veränderter Umstände unzumutbar geworden sein könnte, bildet nicht Gegenstand der Haftprüfung (<ref-ruling> E. 2 S. 221).
3.2 Eine bevorstehende Heirat lässt einen Wegweisungsentscheid als solchen nicht dahinfallen; ebenso wenig das am 25. März 2004 beim Bundesamt für Flüchtlinge eingereichte Wiedererwägungsgesuch. Dies macht der Beschwerdeführer denn auch nicht geltend. Er ist vielmehr der Meinung, dass aufgrund der, wie er behauptet, schon fast abgeschlossenen Hochzeitsvorbereitungen der Vollzug der Wegweisung zum jetzigen Zeitpunkt absolut unverhältnismässig und damit unrechtmässig sei, und weist darauf hin, dass seine Freundin über die Niederlassungsbewilligung verfüge.
Am 17. Oktober 2003 ermächtigte X._ das Zivilstandsamt Basel-Stadt, die von ihm eingereichten heimatlichen Ausweispapiere zur Überprüfung an die für Bangladesh zuständige Schweizer Behörde weiterzuleiten. Gemäss einer Bescheinigung dieses Zivilstandsamts vom 2. Februar 2004 sind einige für die Einleitung des Ehevorbereitungsverfahrens notwendigen Papiere eingereicht worden, andere fehlen noch. Der Beschwerdeführer behauptet in seiner Replik, es fehle einzig noch eine Wohnsitzbescheinigung, und sobald diese vorliege, könnte innerhalb von einigen Wochen ein Heiratstermin der Parteien vereinbart werden. Ob diese Behauptung zutrifft, ist nicht erwiesen; die Formulierung der Bescheinigung der Zivilstandsbehörde lässt vielmehr darauf schliessen, dass noch mehr als ein einziges Dokument ausstehend ist. Auf jeden Fall ist das Vorbereitungsverfahren zur Zeit noch nicht abgeschlossen (Art. 99 Abs. 2 ZGB).
Der Vollzug einer Wegweisung könnte höchstens dann als unverhältnismässig und damit als aus rechtlichen Gründen undurchführbar im Sinne von Art. 13c Abs. 5 lit. a ANAG gelten, wenn sämtliche für die Eheschliessung notwendigen Papiere vorliegen würden und das Zivilstandsamt schon einen konkreten Heiratstermin festgesetzt hätte. In einem solchen Fall wäre eine Ausschaffung in das geographisch doch weit entfernte Bangladesh wohl unverhältnismässig, womit die Ausschaffungshaft zu beenden wäre.
Dies ist aber, wie ausgeführt, vorderhand nicht der Fall, sodass zur Zeit die Ausschaffungshaft als Mittel zur Sicherung des Vollzugs der nach wie vor gültigen Wegweisungsverfügung gerechtfertigt ist.
3.3 Ergibt sich diesbezüglich eine Änderung, etwa indem unterdessen ein Heiratstermin festgelegt wird, so kann der Beschwerdeführer - auch ausserhalb der nach einer Haftgenehmigung geltenden Fristen - ein Gesuch um Haftentlassung stellen.
3.3 Ergibt sich diesbezüglich eine Änderung, etwa indem unterdessen ein Heiratstermin festgelegt wird, so kann der Beschwerdeführer - auch ausserhalb der nach einer Haftgenehmigung geltenden Fristen - ein Gesuch um Haftentlassung stellen.
4. Die Verwaltungsgerichtsbeschwerde ist daher als offensichtlich unbegründet abzuweisen. Dem Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann wegen Aussichtslosigkeit des gestellten Rechtsbegehrens nicht entsprochen werden (Art. 152 Abs. 1 OG). Bei diesem Verfahrensausgang wären die Gerichtskosten grundsätzlich vom Beschwerdeführer zu tragen (Art. 156 Abs. 1 OG). Es rechtfertigt sich indessen, von der Erhebung von Kosten abzusehen.

Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Es werden keine Kosten erhoben.
3. Es werden keine Kosten erhoben.
4. Dieses Urteil wird dem Beschwerdeführer, dem Amt für öffentliche Sicherheit und dem Verwaltungsgericht des Kantons Solothurn sowie dem Bundesamt für Flüchtlinge schriftliche mitgeteilt.
Lausanne, 7. April 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: