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. 