Sachverhalt:
A. X._ (geb. 1962) stammt aus Bangladesch. Er ersuchte 1995 in der Schweiz um Asyl. Die Asylrekurskommission wies am 19. März 1998 seine Beschwerde gegen den entsprechenden negativen Entscheid des Bundesamts für Flüchtlinge vom 4. September 1997 und am 28. Juli 1998 ein Revisionsgesuch hiergegen ab. X._ bemühte sich anschliessend erfolglos um eine Wiedererwägung des Asyl- und Wegweisungsentscheids.
B. B.a Am 21. Mai 2007 ersuchte X._ das Amt für Migration des Kantons Basel-Landschaft, ihm eine Aufenthaltsbewilligung aus humanitären Gründen zu erteilen (Art. 14 Abs. 2 des Asylgesetzes vom 26. Juni 1998 [AsylG; SR 142.31]), worauf ihm dieses mitteilte, dass es dem Bundesamt keinen entsprechenden Antrag auf Zustimmung unterbreiten werde. X._ bat in der Folge am 12. Juni 2009 darum, ihm eine Arbeitsbewilligung auszustellen, was ihm erlauben würde, sich von der Nothilfe zu lösen. Das Amt für Migration und auf Beschwerde hin der Regierungsrat des Kantons Basel-Landschaft lehnten dies am 20. August 2009 bzw. 10. August 2010 ab.
B.b Mit Urteil vom 6. April 2011 bestätigte das Kantonsgericht Basel-Landschaft den entsprechenden Sachentscheid, hob den regierungsrätlichen Beschluss indessen insofern auf, als X._ die unentgeltliche Rechtspflege und Verbeiständung verweigert worden war. Das Gericht ging davon aus, dass X._ gestützt auf den Vorrang des asylrechtlichen Verfahrens (<ref-law>) das Land zu verlassen habe und er mangels Parteistellung im kantonalen Verfahren keine asylrechtliche Härtefallbewilligung erwirken könne (Art. 14 Abs. 2 in Verbindung mit Abs. 4 AsylG). Eine solche bilde nicht Verfahrensgegenstand. Zwar könne ein Berufsverbot den Schutzbereich des durch Art. 8 EMRK garantierten Privatlebens berühren, doch gelte dies nicht für Personen, die - wie X._ - keinen rechtmässigen Aufenthaltstitel besässen und das Land längst hätten verlassen müssen.
C. X._ beantragt vor Bundesgericht, das Urteil des Kantonsgerichts aufzuheben, soweit ihm darin die Arbeitsbewilligung verweigert worden sei; es sei festzustellen, dass das ihm auferlegte Arbeitsverbot Art. 8 EMRK verletze. Er habe alles ihm Zumutbare getan, um in seine Heimat zurückzukehren. Das Bundesamt für Migration habe im Juni 2007 faktisch die Vollzugsbemühungen eingestellt; mangels Reisepapieren sei nicht davon auszugehen, dass die Wegweisung noch in absehbarer Zeit vollzogen werde. Er könne sich bezüglich des Arbeitsverbots deshalb auf den Schutz seines Privatlebens nach Art. 8 EMRK berufen.
Das Kantonsgericht Basel-Landschaft hat darauf verzichtet, sich zur Beschwerde zu äussern. Der Rechtsdienst des Regierungsrats des Kantons Basel-Landschaft und das Bundesamt für Migration beantragen, die Beschwerde abzuweisen.
X._ hat am 20. September 2011 an seinen Ausführungen festgehalten und noch einmal unterstrichen, dass das zuständige Bundesamt "die Vollzugsbemühungen seit Jahren eingestellt" habe und diese "mangels Erfolgsaussichten auch nicht wieder aufgenommen" würden.
D. Der Instruktionsrichter hat am 20. Januar 2012 beim Bundesamt für Migration einen Amtsbericht zur Frage der Möglichkeit des Vollzugs der Wegweisung von X._ eingeholt. Der Bericht vom 8. Februar 2012 geht davon aus, dass die Ausstellung eines Ersatzpapiers durch die bangladeschischen Behörden innert nützlicher Frist möglich sei, wenn X._ seine Haltung ändere und seiner Mitwirkungspflicht bei der Papierbeschaffung nachkomme. Der Regierungsrat des Kantons Basel-Landschaft unterstreicht, dass sich aus der Stellungnahme des Bundesamts "klar" ergebe, dass die Schwierigkeiten bei der Beschaffung von Ersatzpapieren allein auf das (unkooperative) Verhalten von X._ zurückzuführen seien. Unter diesen Umständen bestehe keine Veranlassung, auf die Verweigerung der Erteilung der Arbeitsbewilligung zurückzukommen. Das Kantonsgericht hat auf eine Vernehmlassung zum Amtsbericht verzichtet. X._ macht geltend, das Bundesamt habe das Gericht "nicht richtig" informiert; es unterschlage einzelne wichtige Aktenstücke und gebe anderen "durch aus dem Zusammenhang gerissenen Zitaten" einen falschen Sinn. Trotz seiner Kooperation könne die Wegweisung in absehbarer Zeit nicht vollzogen werden.

Erwägungen:
1. 1.1 Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten ausgeschlossen gegen Entscheide, welche Bewilligungen betreffen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen (<ref-law>), und unter dem gleichen Vorbehalt gegen solche auf dem Gebiet des Asyls, die von einer kantonalen Vorinstanz ausgehen (<ref-law>). Der Beschwerdeführer beantragt nicht, ihm sei eine Aufenthaltsbewilligung in Anwendung von <ref-law> zu erteilen, worauf er keinen Rechtsanspruch hätte und wobei ihm erst im (Zustimmungs-)Verfahren vor dem Bundesamt Parteistellung zukäme (<ref-law>; vgl. aber <ref-ruling> E. 4.3). Auch auf die von ihm beantragte Arbeitsbewilligung, welche regelmässig Teil der Aufenthaltsbewilligung bildet, besteht an sich kein ausländer- oder asylrechtlich begründeter Anspruch (vgl. <ref-law>). Verfahrensgegenstand bildet jedoch die Frage, ob und unter welchen Bedingungen sich ein solcher allenfalls aus Art. 8 EMRK (Recht auf Schutz des Privatlebens) und damit aus dem Völkerrecht ergeben könnte. Der Beschwerdeführer macht gestützt auf die Urteile des Europäischen Gerichtshofs für Menschenrechte (EGMR) Sidabras u. Mitb. gegen Litauen vom 27. Juli 2004 (Nr. 55480/00) und Agraw gegen die Schweiz vom 29. Juli 2010 (Nr. 3295/06) in vertretbarer Weise geltend, dies sei bei ihm wegen der langen Anwesenheit und der Unmöglichkeit des Vollzugs der Wegweisung der Fall. Auf seine Eingabe ist deshalb einzutreten. Ob der behauptete Anspruch tatsächlich besteht, ist eine Frage der materiellen Beurteilung (vgl. <ref-ruling> E. 1.3; <ref-ruling> E. 1.1 S. 179, 497 E. 3.3 S. 500 f.).
1. 1.1 Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten ausgeschlossen gegen Entscheide, welche Bewilligungen betreffen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen (<ref-law>), und unter dem gleichen Vorbehalt gegen solche auf dem Gebiet des Asyls, die von einer kantonalen Vorinstanz ausgehen (<ref-law>). Der Beschwerdeführer beantragt nicht, ihm sei eine Aufenthaltsbewilligung in Anwendung von <ref-law> zu erteilen, worauf er keinen Rechtsanspruch hätte und wobei ihm erst im (Zustimmungs-)Verfahren vor dem Bundesamt Parteistellung zukäme (<ref-law>; vgl. aber <ref-ruling> E. 4.3). Auch auf die von ihm beantragte Arbeitsbewilligung, welche regelmässig Teil der Aufenthaltsbewilligung bildet, besteht an sich kein ausländer- oder asylrechtlich begründeter Anspruch (vgl. <ref-law>). Verfahrensgegenstand bildet jedoch die Frage, ob und unter welchen Bedingungen sich ein solcher allenfalls aus Art. 8 EMRK (Recht auf Schutz des Privatlebens) und damit aus dem Völkerrecht ergeben könnte. Der Beschwerdeführer macht gestützt auf die Urteile des Europäischen Gerichtshofs für Menschenrechte (EGMR) Sidabras u. Mitb. gegen Litauen vom 27. Juli 2004 (Nr. 55480/00) und Agraw gegen die Schweiz vom 29. Juli 2010 (Nr. 3295/06) in vertretbarer Weise geltend, dies sei bei ihm wegen der langen Anwesenheit und der Unmöglichkeit des Vollzugs der Wegweisung der Fall. Auf seine Eingabe ist deshalb einzutreten. Ob der behauptete Anspruch tatsächlich besteht, ist eine Frage der materiellen Beurteilung (vgl. <ref-ruling> E. 1.3; <ref-ruling> E. 1.1 S. 179, 497 E. 3.3 S. 500 f.).
1.2 1.2.1 Der Beschwerdeführer beantragt unter anderem, es sei festzustellen, dass das ihm auferlegte Arbeitsverbot gegen Art. 8 EMRK verstosse. Ein solches Begehren ist bloss zulässig, falls daran ein schutzwürdiges Interesse besteht, das nicht ebenso gut mit einem rechtsgestaltenden Entscheid gewahrt werden kann (vgl. <ref-ruling> E. 2c S. 303 mit Hinweisen; <ref-ruling> E. 3a S. 48). Es ist nicht ersichtlich und der Beschwerdeführer legt nicht dar, inwiefern dies hier der Fall wäre: Heisst das Bundesgericht seine Beschwerde gut, muss der Kanton ihm die umstrittene Arbeitsbewilligung erteilen, ohne dass hierfür die beantragte Feststellung erforderlich wäre. Auf sein entsprechendes Begehren ist nicht einzutreten.
1.2.2 Nicht weiter einzugehen ist auf jene Ausführungen in der Eingabe, die appellatorischen Charakter haben (vgl. <ref-ruling> E. 3 S. 104 f.): Bei der Verletzung von Grundrechten gilt praxisgemäss eine qualifizierte Rügepflicht. Das Bundesgericht prüft eine solche nicht von Amtes wegen, sondern nur soweit sie klar und, falls möglich, belegt dargetan wird; dabei ist jeweils nicht nur (zumindest materiell) auszuführen, welches verfassungsmässige Recht verletzt ist, sondern auch inwiefern es dies sein soll (<ref-law>; <ref-ruling> E. 3.3 S. 310 mit Hinweisen). Der Beschwerdeführer kritisiert die Sachverhaltsfeststellung und die Beweiswürdigung der Vorinstanz hinsichtlich der Vollzugsmöglichkeit seiner Wegweisung; er legt indessen nicht dar, dass und inwiefern diese klar und eindeutig mangelhaft wären. Der eingeholte Amtsbericht enthält keine entsprechenden Hinweise (vgl. unten E. 3.3.2), weshalb im Folgenden grundsätzlich von den sachverhaltsmässigen Feststellungen der Vorinstanz auszugehen ist (vgl. <ref-law>).
2. 2.1 Während der ersten drei Monate nach dem Einreichen eines Asylgesuchs dürfen Asylsuchende keine Erwerbstätigkeit ausüben (<ref-law>). Hernach kann der zuständige Kanton ihnen eine solche gestatten, falls die asylrechtlichen Voraussetzungen (Art. 43 Abs. 1-3 AsylG) gegeben sind, die Wirtschafts- und Arbeitslage die Arbeitsaufnahme erlaubt (vgl. <ref-law> [SR 142.201]), das Gesuch eines Arbeitgebers vorliegt (Art. 18 lit. b AuG), die Vorrangregelung respektiert wird (Art. 21 AuG) und die orts-, berufs- sowie branchenüblichen Lohn- und Arbeitsbedingungen (Art. 22 AuG) eingehalten sind (vgl. GOOD/BOSSHARD, in: Caroni/Gächter/Thurnherr [Hrsg.], Bundesgesetz über die Ausländerinnen und Ausländer [AuG], 2010, N. 80 zu Art. 30 AuG; Schweizerische Flüchtlingshilfe [Hrsg.], Handbuch zum Asyl- und Wegweisungsverfahren, 2009, S. 299 f.). Bei der entsprechenden Arbeitsbewilligung handelt es sich um eine provisorische Befugnis; sie gilt grundsätzlich maximal für die (nicht absehbare) Dauer des Asylverfahrens, während der sich der Betroffene von Gesetzes wegen in der Schweiz aufhalten darf (<ref-law>; vgl. auch CESLA AMARELLE/MINH SON NGUYEN, Les standards d'accueil des personnes soumises au droit d'asile, in: UNHCR [Hrsg.], Schweizer Asylrecht, EU-Standards und internationales Flüchtlingsrecht, 2009, S. 163 ff., dort S. 188 ff. und S. 191 ff.).
2.2 Die Bewilligung erlischt nach Ablauf der mit dem rechtskräftigen negativen Ausgang des Asylverfahrens festgesetzten Ausreisefrist, selbst wenn ein ausserordentliches Rechtsmittel oder ein Rechtsbehelf ergriffen und der Vollzug der Wegweisung ausgesetzt worden ist (<ref-law>). Der Betroffene hat das Land zu verlassen, womit seine Berechtigung, hier zu arbeiten, von Bundesrechts wegen erlischt, es sei denn, das Bundesamt verlängere ihm im ordentlichen Verfahren die Ausreisefrist (vgl. Art. 43 Abs. 2 2. Satz AsylG) oder aber das Departement ermächtige die Kantone, für bestimmte Kategorien von Personen Bewilligungen zur Erwerbstätigkeit über den Ablauf der Ausreisefrist hinaus zu erteilen (<ref-law>; WALTER STÖCKLI, § 11 Asyl, in: Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2. Aufl. 2009, N. 11.42). Mit Zustimmung des Bundesamts kann der Kanton im Rahmen eines asylrechtlichen Härtefalls dem Betroffenen auch eine Aufenthaltsbewilligung gewähren, welche es ihm ermöglicht, einer Erwerbstätigkeit nachzugehen. Hierfür muss er sich ab Einreichen des Asylgesuchs seit mindestens fünf Jahren in der Schweiz aufgehalten haben, sein Aufenthaltsort muss den Behörden zudem immer bekannt gewesen sein; schliesslich hat wegen einer fortgeschrittenen Integration ein schwerwiegender persönlicher Härtefall vorzuliegen (<ref-law>). Diese Regelung gilt nicht nur für hängige, sondern auch für abgeschlossene Asylverfahren (vgl. Schweizerische Flüchtlingshilfe [Hrsg.], a.a.O., S. 240 f.; PETER NIDERÖST, § 9 Sans-Papiers in der Schweiz, in: Ausländerrecht, a.a.O., N. 9.36 f.). Die Gesetzgebung geht grundsätzlich davon aus, dass sich vor Anerkennung eines Härtefalls, die in <ref-law> genannten Ausnahmen vorbehalten, eine Besserstellung bezüglich der Zulassung zur Erwerbstätigkeit nicht rechtfertigt, da hiermit, namentlich für weggewiesene Asylsuchende, welche verpflichtet sind, die Schweiz zu verlassen, ein gegenteiliger Anreiz und ein Grund geschaffen würde, im Land zu verbleiben und die Rückschaffungsbemühungen der Behörden zu erschweren (vgl. die Stellungnahme des Bundesrats vom 18. November 2009 zur am 3. März 2010 abgelehnten Motion 09.3809 van Singer "Arbeitsbewilligung für abgewiesene Asylsuchende").
2.3 Ist der Vollzug der Weg- oder Ausweisung nicht möglich, nicht zulässig oder nicht zumutbar, verfügt das Bundesamt für Migration die vorläufige Aufnahme (Art. 83 Abs. 1 AuG). Diese bildet eine - grundsätzlich zeitlich beschränkte - Ersatzmassnahme, wenn der Vollzug der Wegweisung undurchführbar erscheint. Sie tritt neben die Wegweisung und berührt deren Bestand nicht, sondern setzt ihn voraus. Die vorläufige Aufnahme bildet keine Aufenthaltsbewilligung, sondern einen vorübergehenden Status, der die Anwesenheit regelt, solange der Wegweisungsvollzug nicht zulässig, nicht zumutbar oder nicht möglich erscheint (<ref-ruling> E. 3.1). Eine entsprechende Unmöglichkeit liegt nur bei objektiven Hindernissen vor; es muss klar erkennbar sein, dass der Vollzug der Wegweisung aus technischen oder rechtlichen Gründen auf nicht absehbare Zeit unmöglich sein wird, wobei die Ursachen ausserhalb des Einflussbereichs der betroffenen Person liegen müssen (vgl. Art. 83 Abs. 7 lit. c AuG; Art. 17 VVWA [SR 142.281]; RUEDI ILLES, in: Caroni/Gächter/Thurnherr [Hrsg.], a.a.O., N. 9 und 55 ff. zu Art. 83 AuG). Der Vollzug der Wegweisung gilt in der Praxis zu Art. 83 AuG dann als unmöglich, wenn die weggewiesene Person sich allen vom Kanton hierfür angeordneten Massnahmen unterzogen hat, die Unmöglichkeit des Vollzugs schon ein Jahr dauerte und absehbar erscheint, dass die Vollzugsmassnahmen weiterhin nicht zum Erfolg führen werden (vgl. Schweizerische Flüchtlingshilfe [Hrsg.], a.a.O., S. 236). Die Kantone können vorläufig Aufgenommenen unabhängig von der Arbeitsmarkt- und Wirtschaftslage die Aufnahme einer unselbständigen Erwerbstätigkeit bewilligen (Art. 85 Abs. 6 AuG). Voraussetzung bildet, dass ein Gesuch eines Arbeitgebers vorliegt und die Lohn- und Arbeitsbedingungen eingehalten sind (Schweizerische Flüchtlingshilfe [Hrsg.], a.a.O., S. 307).
3. 3.1 Zu Recht macht der Beschwerdeführer nicht geltend, gestützt auf eine dieser Regelungen über einen Anspruch auf die beantragte Arbeitsbewilligung zu verfügen: Sein Asylgesuch ist abgewiesen und er angehalten worden, das Land zu verlassen, was er bis heute nicht getan hat. Nach dem Ablauf der mit dem rechtskräftigen negativen Ausgang des Asylverfahrens festgesetzten Ausreisefrist erlosch von Bundesrechts wegen seine Möglichkeit, in der Schweiz erwerbstätig zu sein (<ref-law>). Da die kantonalen Behörden (und das Bundesamt) zurzeit noch davon ausgehen, dass ein Wegweisungsvollzug nicht ausgeschlossen erscheint, falls der Beschwerdeführer hierbei kooperiert, war der Kanton Basel-Landschaft bisher nicht bereit, dem Bundesamt zu beantragen, ihn als Härtefall anzuerkennen oder ihn wegen einer Unmöglichkeit des Wegweisungsvollzugs vorläufig aufzunehmen; die damit verbundenen Regeln über eine Zulassung zum Arbeitsmarkt kommen somit nicht zur Anwendung. Unter diesen Umständen darf der Beschwerdeführer zurzeit in der Schweiz nicht arbeiten und kann der Kanton Basel-Landschaft ihm auch keine entsprechende Bewilligung ausstellen. Die Arbeitsberechtigung ist in der Regel an ein Aufenthaltsrecht geknüpft; sie hat keine eigenständige Bedeutung, sondern steht regelmässig in Verbindung mit der Anwesenheitsberechtigung (vgl. PETER UEBERSAX, § 7 Einreise und Aufenthalt, in: Ausländerrecht, a.a.O., N. 7.168).
3. 3.1 Zu Recht macht der Beschwerdeführer nicht geltend, gestützt auf eine dieser Regelungen über einen Anspruch auf die beantragte Arbeitsbewilligung zu verfügen: Sein Asylgesuch ist abgewiesen und er angehalten worden, das Land zu verlassen, was er bis heute nicht getan hat. Nach dem Ablauf der mit dem rechtskräftigen negativen Ausgang des Asylverfahrens festgesetzten Ausreisefrist erlosch von Bundesrechts wegen seine Möglichkeit, in der Schweiz erwerbstätig zu sein (<ref-law>). Da die kantonalen Behörden (und das Bundesamt) zurzeit noch davon ausgehen, dass ein Wegweisungsvollzug nicht ausgeschlossen erscheint, falls der Beschwerdeführer hierbei kooperiert, war der Kanton Basel-Landschaft bisher nicht bereit, dem Bundesamt zu beantragen, ihn als Härtefall anzuerkennen oder ihn wegen einer Unmöglichkeit des Wegweisungsvollzugs vorläufig aufzunehmen; die damit verbundenen Regeln über eine Zulassung zum Arbeitsmarkt kommen somit nicht zur Anwendung. Unter diesen Umständen darf der Beschwerdeführer zurzeit in der Schweiz nicht arbeiten und kann der Kanton Basel-Landschaft ihm auch keine entsprechende Bewilligung ausstellen. Die Arbeitsberechtigung ist in der Regel an ein Aufenthaltsrecht geknüpft; sie hat keine eigenständige Bedeutung, sondern steht regelmässig in Verbindung mit der Anwesenheitsberechtigung (vgl. PETER UEBERSAX, § 7 Einreise und Aufenthalt, in: Ausländerrecht, a.a.O., N. 7.168).
3.2 3.2.1 Diese gesetzliche Regelung steht grundsätzlich im Einklang mit Art. 8 EMRK: Die EMRK verschafft praxisgemäss keinen Anspruch auf Einreise und Aufenthalt oder auf einen besonderen Aufenthaltstitel (<ref-ruling> E. 4.1.1; <ref-ruling> E. 3.1 S. 285 f.; GRABENWARTER/PABEL, Europäische Menschenrechtskonvention, 5. Aufl. 2012, § 22 N. 65 ff. S. 268 ff.; JENS MEYER-LADEWIG, EMRK, 3. Aufl. 2011, N. 64 ff. zu Art. 8 EMRK). Sie hindert die Konventionsstaaten nicht daran, den Aufenthalt auf ihrem Staatsgebiet zu regeln und die Anwesenheit ausländischer Personen unter Beachtung überwiegender Interessen des Familien- oder Privatlebens gegebenenfalls auch wieder zu beenden (vgl. etwa das EGMR-Urteil Gezginci gegen Schweiz vom 9. Dezember 2010 [Nr. 16327/05] § 54 ff.). Dabei darf mitberücksichtigt werden, ob der Aufenthalt im Land rechtmässig war oder nicht (vgl. Urteil 2C_1010/2011 vom 31. Januar 2012 E. 2.4). Das vom Beschwerdeführer angerufene, durch Art. 8 EMRK geschützte Recht zur freien Gestaltung der Lebensführung steht unter einem entsprechenden migrationsrechtlichen Vorbehalt. Zwar impliziert die Möglichkeit, einer Erwerbstätigkeit nachzugehen, auch die Chance, Beziehungen zu anderen aufzubauen und seinen Lebensunterhalt zu verdienen, um das Privatleben nach den eigenen Vorstellungen gestalten zu können, weshalb das Ergreifen eines Berufs und die Möglichkeit, erwerbstätig zu sein, Teil des durch Art. 8 EMRK geschützten Privatlebens bilden kann (EGMR-Urteile Sidabras u. Mitb. gegen Litauen, a.a.O., §§ 42 ff. und Taliadorou gegen Zypern vom 16. Oktober 2008 [Nr. 39627/05] § 54; GRABENWARTER/PABEL, a.a.O., § 22 N. 14 S. 234; MEYER-LADEWIG, a.a.O., N. 31 zu Art. 8 EMRK). Dies führt indessen nicht dazu, dass auch jegliche asyl- oder ausländerrechtliche Beschränkung der Erwerbstätigkeit bereits in den Anwendungsbereich von Art. 8 EMRK fiele. Hiervon ist nur auszugehen, wenn der (weitere) Aufenthalt im Konventionsstaat rechtlich oder zumindest faktisch derart gesichert erscheint, dass das entsprechende Privatleben auch tatsächlich dort gelebt wird. Die vorliegende Problematik ist deshalb - wie die Vorinstanz zu Recht ausgeführt hat - nicht mit dem vom Europäischen Gerichtshof für Menschenrechte im Urteil Sidabras vom 27. Juni 2004 beurteilten Sachverhalt vergleichbar, wo ehemaligen litauischen KGB-Mitgliedern im Rahmen von Lustrationsmassnahmen (vgl. hierzu: MEYER-LADEWIG, a.a.O., N. 32 zu Art. 8 EMRK) verboten worden war, im eigenen Land im öffentlichen Dienst sowie in weiten Teilen der Privatwirtschaft tätig zu werden, was der Gerichtshof im konkreten Fall als konventionswidrig erachtete. Abgewiesene Asylbewerber verfügen über keinen rechtmässigen Aufenthaltstitel im Land, weshalb die damit verbundene Weigerung, ihnen eine Arbeitsbewilligung zu erteilen, regelmässig nicht in den Schutzbereich von Art. 8 EMRK fällt.
3.2.2 Ein entsprechender Anspruch gälte im Übrigen nicht absolut: Gestützt auf Art. 8 Ziff. 2 EMRK ist ein Eingriff in das durch Ziff. 1 geschützte Rechtsgut statthaft, soweit er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ruhe und Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung und zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesellschaft und Moral sowie der Rechte und Freiheiten anderer notwendig ist. Die Konvention verlangt eine Abwägung der sich gegenüberstehenden privaten Interessen an der Bewilligungserteilung einerseits und den öffentlichen an deren Verweigerung andererseits, wobei Letztere in dem Sinne überwiegen müssen, dass sich der Eingriff in einer demokratisch-rechtsstaatlichen Ordnung als notwendig zu erweisen hat (<ref-ruling> E. 2.1 S. 147, 153 E. 2.2.1 S. 156; <ref-ruling> E. 2 S. 6 mit Hinweisen). Die entsprechenden Voraussetzungen sind hinsichtlich des asylrechtlichen Arbeitsverbots in <ref-law> erfüllt: Als schutzwürdiges öffentliches Interesse fällt auch das Durchsetzen einer restriktiven Einwanderungspolitik in Betracht. Eine solche ist mit Blick auf ein ausgewogenes Verhältnis zwischen schweizerischer und ausländischer Wohnbevölkerung, auf die Schaffung günstiger Rahmenbedingungen für die Eingliederung der in der Schweiz bereits ansässigen Ausländer und die Verbesserung der Arbeitsmarktstruktur sowie auf eine möglichst ausgeglichene Beschäftigung im Lichte von Art. 8 Ziff. 2 EMRK zulässig (<ref-ruling> E. 4.1.2 mit Hinweisen). Abgewiesene Asylbewerber verfügen über keine Berechtigung, sich weiter im Land aufzuhalten, womit sie sich von den Asylsuchenden unterscheiden, die von Gesetzes wegen für die Dauer des Verfahrens in der Schweiz verbleiben dürfen (vgl. <ref-law>). Das Arbeitsverbot von <ref-law> unterstreicht die Pflicht, das Land verlassen zu müssen. Würde dem Weggewiesenen eine Arbeitserlaubnis erteilt, stünde dies im Widerspruch zum Wegweisungsentscheid. Das Erwerbsverbot nach <ref-law> bildet eine geeignete Massnahme, um die Konsequenzen des negativen Asylentscheids (Wegweisung) umzusetzen und keine zusätzlichen Anreize für einen rechtswidrigen Verbleib in der Schweiz zu geben. Der damit verbundene Eingriff in allenfalls durch Art. 8 EMRK geschützte Positionen ist regelmässig erforderlich, da eine mildere Massnahme, etwa eine befristete Arbeitsbewilligung, den Wegweisungsentscheid bzw. dessen Vollzug ebenso infrage stellen würde. Für Härtefälle (<ref-law>) bzw. Situationen, bei denen eine Rückkehr oder Ausreise objektiv unmöglich erscheint (vgl. Art. 83 AuG), bestehen Sondernormen, welche die Aufnahme einer Erwerbstätigkeit zulassen (vgl. E. 2.2 und 2.3), womit die Schweiz allfälligen diesbezüglich bestehenden staatlichen Schutzpflichten konventionskonform nachkommt.
3.2.2 Ein entsprechender Anspruch gälte im Übrigen nicht absolut: Gestützt auf Art. 8 Ziff. 2 EMRK ist ein Eingriff in das durch Ziff. 1 geschützte Rechtsgut statthaft, soweit er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ruhe und Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung und zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesellschaft und Moral sowie der Rechte und Freiheiten anderer notwendig ist. Die Konvention verlangt eine Abwägung der sich gegenüberstehenden privaten Interessen an der Bewilligungserteilung einerseits und den öffentlichen an deren Verweigerung andererseits, wobei Letztere in dem Sinne überwiegen müssen, dass sich der Eingriff in einer demokratisch-rechtsstaatlichen Ordnung als notwendig zu erweisen hat (<ref-ruling> E. 2.1 S. 147, 153 E. 2.2.1 S. 156; <ref-ruling> E. 2 S. 6 mit Hinweisen). Die entsprechenden Voraussetzungen sind hinsichtlich des asylrechtlichen Arbeitsverbots in <ref-law> erfüllt: Als schutzwürdiges öffentliches Interesse fällt auch das Durchsetzen einer restriktiven Einwanderungspolitik in Betracht. Eine solche ist mit Blick auf ein ausgewogenes Verhältnis zwischen schweizerischer und ausländischer Wohnbevölkerung, auf die Schaffung günstiger Rahmenbedingungen für die Eingliederung der in der Schweiz bereits ansässigen Ausländer und die Verbesserung der Arbeitsmarktstruktur sowie auf eine möglichst ausgeglichene Beschäftigung im Lichte von Art. 8 Ziff. 2 EMRK zulässig (<ref-ruling> E. 4.1.2 mit Hinweisen). Abgewiesene Asylbewerber verfügen über keine Berechtigung, sich weiter im Land aufzuhalten, womit sie sich von den Asylsuchenden unterscheiden, die von Gesetzes wegen für die Dauer des Verfahrens in der Schweiz verbleiben dürfen (vgl. <ref-law>). Das Arbeitsverbot von <ref-law> unterstreicht die Pflicht, das Land verlassen zu müssen. Würde dem Weggewiesenen eine Arbeitserlaubnis erteilt, stünde dies im Widerspruch zum Wegweisungsentscheid. Das Erwerbsverbot nach <ref-law> bildet eine geeignete Massnahme, um die Konsequenzen des negativen Asylentscheids (Wegweisung) umzusetzen und keine zusätzlichen Anreize für einen rechtswidrigen Verbleib in der Schweiz zu geben. Der damit verbundene Eingriff in allenfalls durch Art. 8 EMRK geschützte Positionen ist regelmässig erforderlich, da eine mildere Massnahme, etwa eine befristete Arbeitsbewilligung, den Wegweisungsentscheid bzw. dessen Vollzug ebenso infrage stellen würde. Für Härtefälle (<ref-law>) bzw. Situationen, bei denen eine Rückkehr oder Ausreise objektiv unmöglich erscheint (vgl. Art. 83 AuG), bestehen Sondernormen, welche die Aufnahme einer Erwerbstätigkeit zulassen (vgl. E. 2.2 und 2.3), womit die Schweiz allfälligen diesbezüglich bestehenden staatlichen Schutzpflichten konventionskonform nachkommt.
3.3 3.3.1 Unter diesen Umständen kann die Verhältnismässigkeit bzw. die Zumutbarkeit der Verweigerung einer konkreten Arbeitsbewilligung nach der Wegweisung im asylrechtlichen Kontext gestützt auf Art. 8 EMRK nur in ausserordentlichen Situationen dennoch problematisch erscheinen. Auf den Schutz des Privat- und Familienlebens können sich in Ausnahmesituationen nach der Rechtsprechung des Europäischen Gerichtshofs für Menschenrechte auch Personen berufen, deren Anwesenheit rechtlich nicht geregelt ist bzw. die allenfalls über kein (gefestigtes) Aufenthaltsrecht verfügen, deren Anwesenheit aber faktisch als Realität hingenommen wird bzw. aus objektiven Gründen hingenommen werden muss. Im Urteil Agraw gegen die Schweiz vom 29. Juli 2010 liess der EGMR die Berufung auf den Schutz des Familienlebens durch ein Ehepaar zu, dessen Asylgesuche erstinstanzlich abgewiesen worden waren und das während fünf Jahren in der Schweiz aus asylrechtlichen Gründen nicht zusammenleben durfte; zum Zeitpunkt der Heirat - so der Gerichtshof - sei klar gewesen, dass die angeordnete Wegweisung nicht in absehbarer Zeit würde vollzogen werden können; die Betroffenen seien für diese Situation nicht verantwortlich gewesen, weshalb die Schweiz ihnen gegenüber - losgelöst von deren Aufenthaltsstatus - die Konventionsgarantien zu erfüllen habe (Ziff. 44; vgl. auch <ref-ruling> E. 6.2 S. 119).
3.3.2 Der Beschwerdeführer hält sich seit 15 Jahren in der Schweiz auf; seit gut 13 Jahren ist es ihm nicht möglich, einer Erwerbstätigkeit nachzugehen, was zur Folge hat, dass er seit dem 1. Januar 2008 von der Nothilfe leben muss (vgl. <ref-ruling> E. 3.1 S. 115 f. mit Hinweisen), welche nur das absolute Existenzminimum deckt und bloss als Überbrückungshilfe für die beschränkte Dauer der Notlage bzw. des Vollzugs der Wegweisung gedacht ist (vgl. <ref-ruling> E. 5.4 und 7.2 - 7.5; <ref-ruling> E. 8.2 S. 181 f.). Das ihm auferlegte Arbeitsverbot greift heute damit, losgelöst von seinem ausländerrechtlichen Status, in einem Mass in sein Recht auf Privatleben (freie Gestaltung der Lebensführung) ein, welches geeignet ist, den normalerweise im Rahmen von Art. 8 Ziff. 2 EMRK gerechtfertigten Sinn und Zweck der Regelung von <ref-law> infrage zu stellen. Das öffentliche Interesse an der Sicherstellung des Asylverfahrens und am Vollzug entsprechender negativer Entscheide vermag nach so langer Dauer des Arbeitsverbots und des faktisch geduldeten Aufenthalts sein privates Interesse, hier erwerbstätig sein zu dürfen und nicht allein von der Nothilfe leben zu müssen, nur dann zu überwiegen, wenn mit dem Vollzug des Wegweisungsentscheids (noch) in absehbarer Zeit ernsthaft gerechnet werden kann bzw. der Beschwerdeführer den Vollzug der Wegweisung bewusst selber weiter verzögert.
3.3.3 Die Vorinstanz ist - wie bereits dargelegt - davon ausgegangen, dass der Vollzug der Wegweisung nach wie vor möglich erscheint und sich die Behörden immer noch darum bemühen. Der Beschwerdeführer tut nicht dar, inwiefern diese Annahme offensichtlich unhaltbar wäre; auch der im vorliegenden Verfahren eingeholte Amtsbericht widerspricht dem nicht klarerweise: Das Bundesamt für Migration betont, dass eine Rückkehr nach Bangladesch möglich erscheine, wenn der Betroffene hierzu bereit sei und er sich über Angehörige ein beglaubigtes "Nationality Certificate" beschaffe, was "problemlos" möglich erscheine. In diesem Fall stelle das Konsulat innert nützlicher Frist ein Ersatzreisepapier aus, mit dem die Heimreise angetreten werden könne. Das vom Beschwerdeführer eingereichte "Nationality Certificate" sei vom Konsulat am 21. Dezember 1999 als ungenügend ("not acceptable") eingestuft worden. Der Vertrauensanwalt habe dem damaligen Bundesamt für Flüchtlinge am 6. Mai 2003 mitgeteilt, dass die vom Beschwerdeführer gelieferten Adressangaben sich als unrichtig erwiesen hätten; das "Nationality Certificate" sei nicht vom zuständigen Amt ausgestellt worden und könne deshalb vom Aussenministerium nicht beglaubigt werden. In der Folge hat sich der Beschwerdeführer zwar wiederholt - wie von ihm verlangt - an seinen Vater gewandt, wobei er diesen um die Beschaffung eines "Nationality Certificate" ersuchte; dabei gab er aber jeweils auch relativ unzweideutig zu verstehen, dass er in der Schweiz verbleiben wolle und nicht bereit sei, in seine Heimat zurückzukehren. Der Beschwerdeführer sprach wiederholt auf dem Konsulat vor; indessen ist nicht klar, was dort diskutiert wurde. Einem Schreiben vom 14. September 2009 lässt sich entnehmen, dass er zwar erklärte, sich in Übereinstimmung mit den Vorgaben des Asylgesetzes zur Beschaffung der nötigen Papiere an das Konsulat wenden zu wollen, er gleichzeitig aber wiederum unterstrich, dass er für einen weiteren Aufenthalt in der Schweiz kämpfe ("so now also i am fighting for stay in Switzerland"). Das Bundesamt erkundigte sich wiederholt bei der bangladeschischen Vertretung nach dem Stand des Verfahrens; doch blieben seine Anfragen vom 5. Juni 2007 bzw. 3. Juni 2011 unbeantwortet. Für die Version des Beschwerdeführers, dass er nie aktiv den Vollzug seiner Wegweisung zu vereiteln versucht habe und die Behörden sich ihrerseits nicht weiter um diesen bemüht hätten, spricht ein Schreiben des Bundesamts für Migration an das Amt für Migration des Kantons Basel-Landschaft vom 29. November 2005, worin es in einem gewissen Widerspruch zu den Ausführungen im Amtsbericht erklärte, dass die Abklärungen durch den Vertrauensanwalt der Schweizer Botschaft in Dhaka ergeben hätten, dass der Beschwerdeführer "aufgrund der vorgelegten Fotos an den angegebenen Adressen" habe identifiziert werden können; es indessen nicht möglich gewesen sei, ein gültiges "Nationality Certificate" zu beschaffen.
3.3.4 In Anwendung von <ref-law> (vgl. E. 1.2.2) ist bei dieser Ausgangslage gesamthaft davon auszugehen, dass der Vollzug der Wegweisung des Beschwerdeführers nach wie vor möglich erscheint und ihm durch das Recht, hier erwerbstätig sein zu können, deshalb im überwiegenden öffentlichen Interesse kein Anlass gegeben werden soll, diesen zu vereiteln. Gleichzeitig ist aber zu unterstreichen, dass das Amt für Migration des Kantons Basel-Landschaft und das Bundesamt für Migration sich mit Nachdruck hierum bemühen müssen; ist der Vollzug innert weniger Monate nicht möglich und bleiben ihre Bemühungen bei den bangladeschischen Behörden ein weiteres Mal ohne Erfolg, ist eine vorläufige Aufnahme des Beschwerdeführers (Unmöglichkeit des Wegweisungsvollzugs) oder bei Vorliegen der entsprechenden Voraussetzungen die Erteilung einer asylrechtlichen Härtefallbewilligung zu prüfen bzw. ihm gestützt auf Art. 8 EMRK in Abweichung von <ref-law> die Möglichkeit einzuräumen, sich seinen Lebensunterhalt hier verdienen zu können, bis ein allfälliger Vollzug der Wegweisung wieder möglich erscheint. Scheitern die Behörden bei ihren Vollzugsbemühungen ein weiteres Mal und kann die Situation des Beschwerdeführers nicht härtefallrechtlich oder im Rahmen einer vorläufigen Aufnahme bereinigt werden, was nicht in den Zuständigkeitsbereich des Bundesgerichts fiele (vgl. <ref-law>), überwiegt sein privates Interesse, sich von der Nothilfe lösen und einer Beschäftigung nachgehen zu können, das öffentliche, ihm mit der Erwerbsmöglichkeit keinen Anreiz zu bieten, illegal im Land zu verbleiben. Es ist zwar grundsätzlich richtig, dass - wie die Vorinstanz ausführt - dem Beschwerdeführer kein Vorteil daraus erwachsen soll, dass er sich während 13 Jahren unrechtmässig in der Schweiz aufgehalten hat, umgekehrt muss die umstrittene Massnahme (Arbeitsverbot) bzw. die damit verbundene Konsequenz (Nothilfeabhängigkeit) im Einzelfall dennoch den konventionsrechtlichen Vorgaben genügen und sich im Rahmen der Interessenabwägung von Art. 8 Ziff. 2 EMRK als verhältnismässig bzw. notwendig erweisen. Dies ist beim Beschwerdeführer nach 13 Jahren Anwesenheit in der Schweiz nicht mehr der Fall, wenn der Vollzug seiner Wegweisung realistischerweise nicht als (unmittelbar) absehbar bezeichnet werden kann.
4. 4.1 Die Beschwerde ist im Sinne dieser Ausführungen abzuweisen, soweit darauf eingetreten wird.
4.2 Da der Beschwerdeführer bedürftig ist und seine Eingabe nicht aussichtslos war, ist seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung zu entsprechen (<ref-law>). Parteientschädigungen sind nicht geschuldet (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird im Sinne der Erwägungen abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
2.1 Es werden keine Kosten erhoben.
2.2 Dem Beschwerdeführer wird Advokat Guido Ehrler, Basel, als unentgeltlicher Rechtsbeistand beigegeben und diesem aus der Gerichtskasse eine Entschädigung von Fr. 2'000.-- ausgerichtet.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Kantonsgericht Basel-Landschaft, Abteilung Verfassungs- und Verwaltungsrecht, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 26. April 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Hugi Yar