Faits:
A.
A.a. A._, né en 1985 et prétendant être de nationalité malienne, a déposé une demande d'asile en Suisse le 4 mai 2004. Par décision du 13 janvier 2005, l'Office fédéral des migrations a rejeté la demande [recte: n'est pas entré en matière sur la demande] et prononcé son renvoi, l'intéressé, qui ne venait manifestement pas du Mali, n'ayant pas rendu vraisemblable qu'il était dans l'impossibilité de présenter des documents d'identité pour des motifs légitimes. A._ n'a pas recouru contre cette décision, qui est ainsi entrée en force, mais a continué à vivre en Suisse où il a bénéficié de prestations d'aide d'urgence depuis le 14 février 2005. A._ a demandé à l'Office fédéral des migrations de reconsidérer sa décision, ce que cette autorité a refusé de faire le 26 octobre 2005.
A.b. Le 7 juillet 2010, le Service de la population du canton de Vaud (ci-après: le Service cantonal) a rejeté la demande de reconnaissance d'un cas de rigueur formulée par A._.
A.c. Depuis le mois de février 2005, A._ a été régulièrement convoqué à des entretiens dans le cadre de l'exécution de son renvoi. Il a en particulier été entendu par trois spécialistes de provenance, qui ont tous estimé que l'intéressé pouvait être originaire de Gambie, deux d'entre eux ayant exclu une possible origine malienne. Il a par ailleurs été présenté à des délégations de Gambie, du Mali et du Sénégal, sans qu'aucune d'entre elles ne l'ait reconnu comme l'un de ses ressortissants. Le 7 octobre 2011, l'Office fédéral des migrations a indiqué au Service cantonal que A._ serait une nouvelle fois présenté à une délégation du Mali. L'arrêt attaqué retient toutefois qu'aucune démarche n'aurait été entreprise par les autorités d'exécution du renvoi depuis septembre 2011, soit depuis deux ans.
B.
Le 3 juillet 2012, A._ a demandé au Service cantonal l'autorisation de travailler, ce que cette autorité lui a refusé par décision du 22 avril 2013. L'intéressé a interjeté recours contre cette décision en se fondant sur l'art. 8 CEDH auprès de la Cour de droit administratif et public du Tribunal cantonal vaudois (ci-après: le Tribunal cantonal), qui l'a rejeté par arrêt du 23 septembre 2013. En substance, le Tribunal cantonal a retenu qu'en tant que requérant d'asile débouté en séjour en Suisse depuis 9 ans et bénéficiant de l'aide d'urgence depuis 8 ans, A._ subissait certes une atteinte importante à sa vie privée au sens de l'art. 8 CEDH en étant contraint de ne vivre que de l'aide d'urgence, mais que cette atteinte était proportionnée au but d'intérêt public consistant à chercher à exécuter son renvoi. Ce but devait primer son intérêt privé à être autorisé à travailler, l'exécution du renvoi devant être considérée en l'espèce comme toujours possible dans un certain délai, le fait que les autorités d'exécution n'aient apparemment plus entrepris de démarche pour exécuter le renvoi de l'intéressé depuis deux ans ne suffisant pas à considérer que tel n'était pas le cas. Au demeurant, cette mesure était retardée du fait même de l'intéressé qui ne collaborait pas, mais fournissait des informations erronées sur son origine.
C.
Contre cet arrêt, A._ recourt auprès du Tribunal fédéral à qui il demande, sous suite de dépens, d'admettre son recours et d'annuler l'arrêt du Tribunal cantonal du 23 septembre 2013. Il requiert également l'assistance judiciaire partielle, à savoir limitée aux frais de la procédure.
Le Service cantonal renonce à se déterminer sur le recours. Le Tribunal cantonal se réfère à l'arrêt attaqué. L'Office fédéral des migrations conclut au rejet du recours.

Considérant en droit:
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>). Il contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 44).
1.1. Le présent recours, adressé aux Cours sociales du Tribunal fédéral, a été transmis à la II e Cour de droit public du Tribunal fédéral comme objet de sa compétence (cf. art. 30 al. 1 du Règlement du Tribunal fédéral; RS 173.110.131).
1.2. Le recourant a simplement déclaré former un " recours " auprès du Tribunal fédéral. Cette désignation imprécise ne saurait lui nuire à condition que le recours remplisse les exigences légales de la voie de droit qui lui est ouverte (cf. <ref-ruling> consid. 1.1 p. 370; <ref-ruling> consid. 2.1 p. 491).
1.3. Selon l'art. 83 let. d ch. 2 LTF, le recours en matière de droit public est irrecevable contre une décision en matière d'asile rendue par une autorité cantonale précédente et dont l'objet porte sur une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit; selon l'art. 83 let. c ch. 2 LTF, il est également irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Dès lors que le recourant invoque de manière défendable un droit découlant de l'art. 8 CEDH (cf. arrêt 2C_459/2011 du 26 avril 2012 consid. 1.1 non publié in <ref-ruling>; arrêt 2C_1147/2013 du 13 décembre 2013 consid. 4), la voie du recours en matière de droit public lui est ouverte, étant précisé que la question de savoir si le recourant peut effectivement se prévaloir de l'art. 8 CEDH est une question de droit matériel et non de recevabilité (<ref-ruling> consid. 1.3 p. 287; arrêt 2C_878/2013 du 13 février 2014 consid. 1.1).
1.4. Le recourant formule des conclusions purement cassatoires. Celles-ci sont toutefois admissibles dès lors que l'on comprend clairement, à la lecture du mémoire, que le recourant entend obtenir du Tribunal fédéral l'autorisation d'exercer une activité lucrative (cf. arrêts 2C_683/2013 du 13 février 2014 consid. 2.3; 1C_571/2012 du 26 novembre 2013 consid. 1.3).
1.5. Pour le surplus, l'arrêt attaqué est une décision finale (<ref-law>), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Le recours a par ailleurs été déposé en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'<ref-law>. Il convient donc d'entrer en matière.
2.
Saisi d'un recours en matière de droit public, le Tribunal fédéral contrôle librement le respect du droit fédéral et du droit international (cf. art. 95 let. a et b et <ref-law>), sous réserve des exigences de motivation figurant à l'<ref-law>, selon lequel le Tribunal fédéral n'examine la violation des droits fondamentaux que si le grief a été invoqué et suffisamment motivé par le recourant. L'acte de recours doit alors, sous peine d'irrecevabilité, contenir un exposé succinct des droits et principes constitutionnels violés et préciser en quoi consiste la violation (<ref-ruling> consid. 2.2 p. 232; <ref-ruling> consid. 2.5 p. 314).
3.
Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus par l'<ref-law>. Il ne peut s'en écarter que si les constatations de ladite autorité ont été établies de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 7.1 p. 51; <ref-ruling> consid. 4.1.2 p. 62) - ou en violation du droit au sens de l'<ref-law> (<ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>). Par ailleurs, aucun fait nouveau ni preuve nouvelle ne peut être présenté, à moins de résulter de la décision de l'autorité précédente (<ref-law>).
Le recourant présente, en particulier sous le titre " En fait " de son mémoire, sa propre version des événements. Dans la mesure où celle-ci s'écarte des faits constatés par le Tribunal cantonal sans que le recourant n'invoque ni a fortiori ne démontre en quoi ce dernier les aurait établis arbitrairement, le Tribunal fédéral statuera exclusivement sur la base des faits tels qu'ils ressortent de l'arrêt attaqué.
4.
Le litige porte sur le point de savoir si l'interdiction de travailler du recourant, confirmée par l'arrêt attaqué, est conforme à l'art. 8 CEDH.
Il convient au préalable de rappeler les règles applicables en la matière en droit suisse.
4.1. Un requérant d'asile n'a pas le droit d'exercer d'activité lucrative pendant les trois premiers mois qui suivent le dépôt de sa demande d'asile (art. 43 al. 1 de la loi fédérale sur l'asile; LAsi; RS 142.31). Il peut ensuite être autorisé à exercer une activité lucrative (cf. art. 43 al. 2 et 3 LAsi). L'autorisation est provisoire et n'est valable que pour la durée de la procédure d'asile au plus, période durant laquelle l'étranger a un droit de séjour en Suisse (<ref-ruling> consid. 2.1 p. 248). Elle s'éteint ainsi à l'expiration du délai fixé au requérant pour quitter le pays (délai de départ), même si ce dernier a fait usage d'une voie de droit extraordinaire et que l'exécution du renvoi a été suspendue (art. 43 al. 2 première phrase LAsi; <ref-ruling> consid. 2.2 p. 248). Le requérant peut toutefois encore être autorisé à travailler si l'Office fédéral des migrations prolonge le délai pour quitter le pays lors de la procédure ordinaire (art. 43 al. 2 deuxième phrase LAsi); ensuite, le Département fédéral de justice et police peut habiliter les cantons à prolonger, au-delà du délai de départ, les autorisations d'exercer une activité lucrative de certaines catégories de personnes lorsque des circonstances particulières le justifient (cf. <ref-law>).
Le canton peut octroyer une autorisation de séjour à toute personne qui lui a été attribuée dans des cas de rigueur graves aux conditions de l'<ref-law> et sous réserve de l'approbation de l'Office fédéral des migrations. Une telle autorisation de séjour confère également à la personne concernée la possibilité d'exercer une activité lucrative et s'applique tant aux personnes dont les procédures d'asile sont pendantes qu'à celles dont les procédures d'asile sont achevées (<ref-ruling> consid. 2.2 p. 248 s.).
Finalement, les étrangers dont l'exécution du renvoi ou de l'expulsion n'est pas possible, n'est pas licite ou ne peut être raisonnablement exigée sont mis au bénéfice d'une admission provisoire en Suisse (art. 83 al. 1 LEtr). Il s'agit d'un statut précaire, qui ne constitue pas une autorisation de séjour (<ref-ruling> consid. 2.3 p. 249; arrêt 2C_639/2012 du 13 février 2013 consid. 1.2.1). Le renvoi est réputé impossible s'il est dû à des empêchements objectifs. Il doit ainsi être clairement reconnaissable que son exécution sera impossible pour des motifs techniques ou juridiques pour une période non prévisible (<ref-ruling> consid. 2.3 p. 249) et non pas en raison du comportement de l'étranger (art. 83 al. 7 let. c LEtr). Les personnes admises provisoirement peuvent obtenir de la part des autorités cantonales une autorisation d'exercer une activité lucrative (art. 85 al. 6 LEtr).
4.2. Il découle de ces règles que l'autorisation de travailler n'a en principe pas de portée autonome, mais qu'elle est liée à l'existence d'un droit de présence en Suisse (<ref-ruling> consid. 3.1 p. 250). C'est dès lors à juste titre que le recourant ne se fonde pas sur l'une de ces dispositions pour requérir une autorisation de travailler. Sa demande d'asile a fait l'objet d'une décision de non-entrée en matière en 2005 et il s'est vu impartir un délai pour quitter la Suisse, ce qu'il n'a pas fait jusqu'à ce jour; la possibilité d'exercer une activité lucrative s'est ainsi éteinte à l'expiration du délai qui lui a été fixé pour quitter le pays (<ref-law>). Le recourant a par ailleurs déjà sollicité, en vain, une autorisation de séjour pour cas de rigueur au sens de l'<ref-law> (cf. supra consid. A.b.). Finalement, il ressort de l'arrêt attaqué que les autorités cantonales sont d'avis que le renvoi est possible et qu'il est retardé du fait du comportement du recourant, de sorte que l'admission provisoire au sens de l'art. 83 al. 1 LEtr n'entre pas en ligne de compte.
5.
Le recourant soutient, en se référant à l'arrêt du Tribunal du 26 avril 2012 (<ref-ruling>), à la jurisprudence de la Cour européenne des droits de l'homme et à la directive 2008/115/CE du Parlement européen et du Conseil du 16 décembre 2008 relative aux normes et procédures communes applicables dans les Etats membres au retour des ressortissants de pays tiers en séjour irrégulier (ci-après: Directive sur le retour) que l'arrêt attaqué viole son droit au respect de sa vie privée (art. 8 par. 1 CEDH) d'une manière disproportionnée eu égard à la durée de sa présence en Suisse et de l'absence de perspectives d'exécution de son renvoi dans un délai prévisible. Il soutient, en substance, que son intérêt privé à obtenir une autorisation de travailler prime l'intérêt public à l'exécution du renvoi, les autorités ne prenant plus aucune mesure à cet effet depuis deux ans.
5.1. Dans son arrêt du 26 avril 2012 (<ref-ruling>), le Tribunal fédéral a jugé que les requérants d'asile déboutés, qui ne disposent pas d'un titre de séjour valable et qui se voient de ce fait privés de la possibilité d'obtenir une autorisation de travailler, ne tombent en principe pas dans le champ d'application de l'art. 8 CEDH. Dans des circonstances exceptionnelles, l'interdiction de travail qui leur est imposée constitue toutefois une ingérence dans le droit au respect de leur vie privée, si la poursuite du séjour dans l'Etat apparaît en droit ou à tout le moins dans les faits comme assurée, de sorte qu'il y a lieu d'admettre que la vie privée a lieu dans cet Etat (<ref-ruling> consid. 3.2.1 p. 251). Pareille ingérence est néanmoins admissible aux conditions de l'art. 8 par. 2 CEDH, notamment si l'intérêt public à l'application de la mesure prime l'intérêt privé du requérant d'asile débouté, ce qui est en principe le cas, l'interdiction de travailler apparaissant comme une mesure adaptée pour mettre en oeuvre les conséquences d'une décision négative en matière d'asile et éviter de conférer un attrait supplémentaire à la poursuite du séjour illégal en Suisse (<ref-ruling> consid. 3.2.2 p. 252). Ce n'est qu'exceptionnellement, si le renvoi ne peut être mis en oeuvre dans un délai prévisible, qu'une telle ingérence peut être problématique sous l'angle de sa proportionnalité (<ref-ruling> consid. 3.3.1). Il s'agissait dans cet arrêt d'un requérant d'asile débouté qui était resté en Suisse pendant 15 ans, dénué d'autorisation d'exercer une activité lucrative depuis 13 ans et qui vivait depuis cinq ans de l'aide d'urgence. Le Tribunal fédéral a souligné qu'avec une si longue interdiction de travailler, l'intérêt public consistant à assurer le déroulement de la procédure d'asile et l'exécution des décisions négatives ne pouvait l'emporter sur l'intérêt privé du recourant à pouvoir être actif et à ne pas devoir vivre uniquement de l'aide d'urgence, sauf si l'exécution de la décision de non-entrée en matière semblait pouvoir encore être mise en oeuvre dans un certain délai, respectivement lorsque le recourant retardait volontairement l'exécution de la décision (<ref-ruling> consid. 3.3.2 et 3.3.3 p. 253 s.; cf. également arrêt 2C_1147/2013 du 13 décembre 2013 consid. 2).
5.2. En l'espèce, le recourant, en Suisse depuis plus de neuf ans, au bénéfice de l'aide d'urgence et ne pouvant plus exercer une activité lucrative depuis plus de huit ans, a participé, entre 2011 et 2013, à plusieurs mesures qui lui ont permis d'obtenir une rémunération mensuelle de 150 fr. qui est venue s'ajouter à l'aide d'urgence. L'arrêt attaqué admet que l'interdiction de travailler du recourant constitue une ingérence dans sa vie privée au sens de l'art. 8 par. 1 CEDH, bien que ce dernier ne puisse se prévaloir d'une présence en Suisse et d'une interdiction de travailler aussi longs que dans l'<ref-ruling>. Pour le Tribunal cantonal, l'intérêt public au maintien de cette mesure prime l'intérêt privé du recourant à exercer une activité lucrative, l'exécution du renvoi n'étant pas encore intervenue en raison de l'absence de collaboration de l'intéressé qui, régulièrement convoqué à des entretiens depuis février 2005 dans le but de déterminer sa véritable nationalité, fournit des indications erronées sur son origine. Le fait que deux ans se soient vraisemblablement écoulés depuis la dernière démarche entreprise par les autorités pour mettre en oeuvre l'exécution du renvoi ne permet pas encore de conclure que le renvoi ne peut être mis en oeuvre dans un certain délai, le recourant étant au demeurant responsable de cette situation en raison de son défaut de collaboration et du fait qu'il n'a entrepris aucune démarche pour retourner dans son pays d'origine.
5.3. L'appréciation du Tribunal cantonal procède d'une correcte application du droit et de la jurisprudence au cas d'espèce. Il ressort en effet des faits de l'arrêt attaqué, que le recourant conteste en vain par des arguments de nature appellatoire et, partant, irrecevables (cf. supra consid. 3), que c'est bien son absence de collaboration qui explique l'inexécution de son renvoi, de sorte que l'intéressé ne saurait se prévaloir de son long (et illégal) séjour en Suisse (qui est toutefois d'un peu plus de neuf ans, alors qu'il était de quinze ans dans l'arrêt <ref-ruling>, cf. consid. 3.3.2 p. 253) pour faire valoir avec succès que l'interdiction de travailler constituerait une ingérence disproportionnée et, partant, inadmissible, dans sa vie privée. Il convient de rappeler qu'entre 2011 et 2013, le recourant a pu obtenir un revenu supplémentaire en participant à certaines mesures.
5.4. Le Tribunal fédéral a toutefois insisté, dans l'<ref-ruling> (cf. consid. 3.3.4, p. 255), sur le fait que les autorités d'exécution du renvoi devaient s'efforcer avec fermeté de mettre en oeuvre le renvoi de requérants d'asile déboutés. Il a retenu, dans cette affaire, que si les efforts desdites autorités auprès de la représentation de l'Etat d'origine du recourant devaient s'avérer vains et le renvoi impossible dans les prochains mois, il conviendrait alors de faire primer l'intérêt privé du recourant à pouvoir travailler et d'envisager ainsi une admission provisoire (art. 83 LEtr), une reconnaissance d'un cas de rigueur (<ref-law>) ou une autorisation de travailler sur la base de l'art. 8 CEDH et en dérogation à l'<ref-law>, jusqu'à ce que l'exécution du renvoi paraisse à nouveau possible.
En l'espèce, l'appréciation du Tribunal cantonal selon laquelle le seul écoulement de deux ans depuis la dernière démarche entreprise ne suffit pas à considérer que le renvoi ne peut être mis en oeuvre dans un certain délai est discutable, mais ne saurait suffire, en l'état, à l'admission du recours, compte tenu du défaut de collaboration du recourant. Il convient en revanche de rappeler aux autorités d'exécution qu'elles doivent prendre régulièrement des mesures pour mettre en oeuvre le renvoi, sans quoi l'interdiction de travailler et son corollaire, la dépendance à l'aide d'urgence, pourrait à l'avenir, étant donné le nombre d'années déjà important de présence en Suisse du recourant, s'avérer disproportionnée.
5.5. Les autres arguments du recourant ne peuvent par ailleurs pas être suivis. Le recourant invoque l'arrêt de la Cour européenne des droits de l'homme Agraw contre Suisse du 29 juin 2010 (publié in PJA 2011 p. 557), dans lequel un couple de requérants d'asile déboutés a invoqué avec succès l'art. 8 CEDH pour pouvoir vivre ensemble en Suisse. Cet arrêt se distingue du cas d'espèce notamment parce que le renvoi ne pouvait pas être mis en oeuvre dans un délai prévisible et sans que les intéressés ne soient responsables de cette situation (voir aussi <ref-ruling> consid. 6.2 p. 119). La problématique de l'arrêt Sidabras contre Lituanie du 27 juillet 2004 (publié in Recueil CourEDH 2004-VIII p. 399) est également différente de celle du recourant, puisqu'il concerne la question de savoir si des ressortissants d'un Etat peuvent se voir interdire de travailler, dans leur pays, dans le secteur public et dans plusieurs domaines privés; il en va de même de l'arrêt Niemietz contre Allemagne du 16 décembre 1992 (publié in EuGRZ 1993 p. 65), également cité par le recourant, qui traite le point de savoir si la perquisition dans un cabinet d'avocat est susceptible de constituer une ingérence dans la vie privée. Finalement, c'est également en vain que le recourant invoque la Directive sur le retour, celui-ci ne démontrant pas en quoi ce texte lui conférerait une protection supérieure à celle de l'art. 8 CEDH. Il ne saurait par ailleurs tirer aucun droit au travail de l'art. 6 de cette Directive, qui traite de la simple possibilité (et non pas d'une obligation), pour les Etats membres, de décider d'accorder un droit de séjour ou une autorisation conférant un droit de séjour pour des motifs charitables, humanitaires ou autres à un ressortissant d'un pays tiers en séjour irrégulier sur son territoire.
6.
Les considérants qui précèdent conduisent au rejet du recours. Vu l'issue de la procédure, le recourant devrait en supporter les frais (<ref-law>). Compte tenu des circonstances et du fait que le recours n'était pas d'emblée voué à l'échec, il convient toutefois d'admettre la demande d'assistance judiciaire partielle formulée et de le dispenser de payer les frais judiciaires (<ref-law>). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire partielle est admise.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le présent arrêt est communiqué au représentant du recourant, au Service de la population et au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 24 mars 2014
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant: Seiler
La Greffière: Vuadens