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.