Faits:
A.
A.a. A._, né en 1973 et prétendant être ressortissant de la Sierra Leone, a déposé une demande d'asile en Suisse le 30 août 2001. Par décision du 23 novembre 2001, l'Office fédéral des migrations n'est pas entré en matière sur la demande et a prononcé son renvoi de Suisse, au motif que l'intéressé avait trompé les autorités sur son origine et son identité, un rapport d'expertise du 14 septembre 2001 ayant retenu que sa socialisation prédominante avait eu lieu au Ghana et non pas en Sierra Leone. A._ a retiré le recours qu'il avait déposé contre cette décision auprès de la Commission suisse de recours en matière d'asile. Par décision du 1 er décembre 2004 confirmée sur recours par dite Commission le 1 er mars 2005, l'Office fédéral des migrations a déclaré irrecevable la demande de reconsidération de la décision du 23 novembre 2001 formulée par A._.
A.b. Le 4 avril 2007, A._ a sollicité une autorisation de séjour pour cas de rigueur auprès du Service de la population du canton de Vaud (ci-après: le Service cantonal), qui a toutefois refusé de transmettre cette demande à l'Office fédéral des migrations.
A._ a encore sollicité à trois reprises (soit les 29 juillet 2009, 19 mai 2010 et 15 novembre 2011) et en vain de l'Office fédéral des migrations la reconsidération de la décision de non-entrée en matière du 23 novembre 2001. Il a formé recours contre les deux premiers refus de cette autorité auprès du Tribunal administratif fédéral, qui les a déclarés irrecevables par arrêts des 18 décembre 2009 et 7 juillet 2010.
Le 10 juillet 2012, A._ a requis une seconde fois du Service cantonal la délivrance d'une autorisation de séjour pour cas de rigueur, qui lui a été refusée par décision du 10 janvier 2013.
A.c. A._ a d'abord été convoqué le 29 janvier 2002 pour un entretien relatif à son départ. Il a ensuite été auditionné le 5 mars 2002 par un spécialiste de provenance, qui a estimé qu'il connaissait mal la Sierra Leone et qu'il était difficile d'établir son pays d'origine, puis, le 18 juin 2003, par un autre spécialiste de provenance; selon le compte-rendu de cet entretien, le recourant a vécu au Ghana comme réfugié et son pays d'origine est très difficile à déterminer. Le 4 août 2004, A._ a été convoqué pour un entretien auprès de l'Ambassade du Ghana. Le 9 août 2004, l'Office fédéral des migrations l'a informé que sa prétendue origine sierra léonaise était peu crédible étant donné le caractère lacunaire de ses indications et connaissances au sujet de ce pays, d'autant plus que les experts linguistiques avaient estimé qu'il était plutôt originaire du Ghana. Le 23 août 2006, A._ a participé à une audition par devant une délégation des autorités ghanéennes, qui l'a classé comme " cas de vérification ", des contrôles devant encore être effectués dans le pays. Dès lors que A._ affirmait être citoyen de la Sierra Leone, il a été présenté le 27 février 2008 à une délégation de cet Etat, qui ne l'a pas reconnu, mais affirmé qu'il parlait un dialecte du Libéria. Le 24 juin 2009, il a été présenté à un représentant de l'Ambassade du Ghana, qui ne l'a toujours pas reconnu comme un de ses ressortissants, mais qui s'est engagé à procéder aux vérifications nécessaires. Le 12 avril 2010, l'Office fédéral des migrations, sans nouvelles des autorités ghanéennes malgré une relance le 4 août 2009, a informé le Service cantonal qu'il entendait présenter l'intéressé une nouvelle fois aux représentants de l'Ambassade du Ghana, le personnel ayant changé l'année précédente, ainsi qu'aux autorités du Libéria. Le 30 novembre 2010, A._ a été présenté pour une troisième fois à un représentant de l'Ambassade du Ghana, qui ne l'a pas reconnu. Le 11 octobre 2011, il a été auditionné par un autre spécialiste de provenance, qui a conclu, notamment au vu de ses caractéristiques linguistiques, qu'il venait probablement du Ghana. Le 27 juin 2012, A._ a été entendu pour la deuxième fois par une délégation sierra léonaise, qui ne l'a pas reconnu et estimé que l'intéressé était originaire du Libéria. Dès lors, l'Office fédéral des migrations a informé le Service cantonal le 3 juillet 2012 que A._ serait présenté à la prochaine audition centralisée auprès d'une délégation du Libéria. Le 13 mai 2013, la date de cette audition n'était pas encore arrêtée.
A.d. Durant son séjour en Suisse, A._ a été assisté financièrement et a été au bénéfice de l'aide d'urgence à compter de mai 2004.
B.
Le 3 juillet 2012, A._ a sollicité du 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.
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 conclut au rejet du recours en se référant à 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 grave 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 2001; 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>). Les quatre demandes de reconsidération de cette non-entrée en matière se sont soldées par un échec. Le recourant a par ailleurs déjà sollicité à deux reprises, 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é en partie 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 du fait de l'absence de perspectives réalistes d'exécution de son renvoi. Il en conclut que son intérêt privé à obtenir une autorisation de travailler doit primer l'intérêt public à l'exécution de son renvoi.
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 p. 252 s.). Il s'agissait dans cet arrêt d'un requérant d'asile débouté qui était resté en Suisse pendant quinze ans, dénué d'autorisation d'exercer une activité lucrative depuis treize 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êts 2C_1017/2013 du 24 mars 2014 consid. 5.1; 2C_1147/2013 du 13 décembre 2013 consid. 2).
5.2. En l'espèce, 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 (12 ans) et d'une interdiction de travailler (9 ans) aussi longues que dans l'<ref-ruling> (de respectivement 15 et 13 ans), soulignant en revanche que la période passée au bénéfice de l'aide d'urgence (9 ans) était bien plus longue que celle prise en compte dans cet arrêt (5 ans) et qu'il apparaissait que le recourant n'avait pas pu participer à des programmes d'occupation qui lui auraient permis d'obtenir un pécule en sus de l'aide d'urgence.
Pour le Tribunal cantonal, l'intérêt public au maintien de cette mesure prime toutefois l'intérêt privé du recourant à exercer une activité lucrative. A l'appui de cette appréciation, l'arrêt attaqué retient d'abord que si le recourant a été présenté en vain à plusieurs reprises devant des autorités ghanéennes et sierra léonaises, il doit encore l'être à une délégation du Libéria, de sorte que la décision de renvoi semble encore pouvoir être exécutée. Il relève ensuite que les autorités suisses ont fait preuve de diligence depuis 2002 pour exécuter le renvoi, mettant en oeuvre de multiples mesures d'instruction en vue de déterminer l'Etat d'origine du recourant. Finalement, les juges cantonaux considèrent que ce dernier, persistant à dissimuler son identité et sa nationalité, doit être tenu pour partie responsable de la situation dans laquelle il se trouve. Il n'a ainsi jamais établi avoir accompli une quelconque démarche pour obtenir des papiers d'identité ni rendu vraisemblable que la position des autorités de la Sierra Leone serait injustifiée, voire abusive, pas plus qu'il n'a prouvé avoir fourni toutes les informations voulues aux diverses délégations auxquelles il a été présenté.
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.
5.3.1. Les juges cantonaux ont relevé à juste titre que les autorités suisses avaient fait preuve de diligence depuis 2002 en vue d'exécuter la décision de renvoi prononcée à l'encontre du recourant. En effet, depuis la décision de non-entrée en matière du 23 novembre 2001, celui-ci a été auditionné ou présenté à des délégations des autorités ghanéennes ou sierra léonaises une dizaine de fois. L'arrêt attaqué retient par ailleurs qu'il est prévu que le recourant soit présenté à la prochaine audition centralisée auprès d'une délégation du Libéria et aucun élément ne permet de considérer que cette audition n'aura pas lieu dans un délai raisonnable. En pareilles circonstances, retenir, comme le fait l'arrêt attaqué, que la décision de renvoi peut encore être exécutée ne porte pas le flanc à la critique, contrairement à ce que soutient le recourant.
5.3.2. Par ailleurs, ce dernier conteste en vain, par des arguments de nature appellatoire et, partant, irrecevables (cf. supra consid. 3), que c'est à tout le moins en partie 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 de neuf ans, alors qu'il était de quinze ans dans l'arrêt publié aux <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.
5.3.3. Les autres arguments du recourant ne peuvent par ailleurs pas être suivis. Le recourant invoque en vain l'arrêt Sidabras contre Lituanie du 27 juillet 2004 (publié in Recueil CourEDH 2004-VIII p. 399), cet arrêt traitant 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. Finalement, c'est également en vain que le recourant invoque la Directive sur le retour, le recourant 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.
5.4. Contrairement à une affaire similaire récemment jugée par la Cour de céans (arrêt 2C_1017/2013 du 24 mars 2014), où les autorités d'exécution du renvoi étaient restées inactives durant deux ans, on ne se trouve pas en l'espèce dans un tel cas de figure, lesdites autorités ayant au contraire pris régulièrement et encore récemment des mesures pour déterminer l'Etat d'origine du recourant. Par ailleurs, aucun élément ne permet de douter que les autorités vont continuer leurs efforts en vue du renvoi, comme l'exige la jurisprudence (cf. <ref-ruling> consid. 3.3.4 p. 255), ni que celui-ci apparaît en l'état impossible. Partant, on ne se trouve pas encore dans une situation où il se justifierait, à titre exceptionnel, de faire primer l'intérêt privé du recourant à pouvoir travailler.
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 17 avril 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