Faits:
A.
A.a. S._, soudeur de formation, a travaillé en qualité d'ouvrier polyvalent au service de l'entreprise X._ à Z._. Il a été victime de plusieurs accidents qui ont entraîné diverses atteintes à la santé. S._ n'a plus exercé d'activité lucrative après un accident survenu le 18 mars 2000 (qui a entraîné une entorse du Lisfranc à droite et une fracture à la base du 1 er métatarsien du pied droit), à l'exception d'une tentative de retour au travail entre les 12 et 18 octobre 2000.
Dans un rapport du 4 mars 2001, la doctoresse V._, rhumatologue, a diagnostiqué une cervico-brachialgie droite chronique sur péri-arthropathie scapulo-humérale chronique, un status après section du long fléchisseur du pouce droit et des deux nerfs collatéraux, un status après hémolyse du long fléchisseur propre du pouce droit et réfection de poulie à l'aide d'une partie du tendon du grand palmaire, un status après fracture oblique modérément déplacée basale de l'annulaire droit, ostéosynthésée le 30 janvier 1992, un status après entorse vertébrale dorsale haute en 1990, un status après épicondylite droite post-traumatique en 1997, des douleurs chroniques au pied droit sur status après entorse du Lisfranc du pied droit avec fracture à la base du 1er métatarsien le 18 mars 2000 et algoneurodystrophie du pied droit, ainsi qu'un état anxio-dépressif. La doctoresse V._ a estimé que, sur le plan strictement rhumatologique, la capacité de travail était de 50 % avec une possibilité d'augmentation ultérieure à 75 %, voire à 100 %. Elle a suggéré qu'une appréciation pluridisciplinaire du cas soit faite pour évaluer l'incidence de l'état anxio-dépressif et d'un possible trouble de l'adaptation sur la capacité de travail.
Le docteur C._, spécialiste en maladies vasculaires, a constaté une insuffisance artérielle bilatérale des membres inférieurs avec une artériopathie occlusive touchant principalement l'étage fémoral, cette localisation expliquant les douleurs jambières à la marche (rapport du 19 novembre 2007). Le docteur M._, cardiologue, a nié l'existence de maladies coronariennes significatives (rapport du 4 décembre 2007) et le docteur F._, diabétologue, a constaté une évolution favorable du diabète (rapport du 19 décembre 2007).
A.b. Le 29 mai 2008, S._ a déposé une demande de prestations de l'assurance-invalidité auprès de l'Office de l'assurance-invalidité pour le canton de Vaud (ci-après: l'office AI).
Le docteur P._, généraliste et médecin traitant, a diagnostiqué, avec répercussion sur la capacité de travail, un status après entorse de Lisfranc et fracture de la base du 1er métatarsien non déplacé et du sésamoïde interne le 18 mars 2000, un status après algoneurodystrophie de stade I du pied droit avec résolution de la pathologie confirmée par scintigraphie osseuse et IRM, un état anxio-dépressif et des lombalgies sur troubles dégénératifs et canal lombaire étroit, ainsi que, sans répercussion sur la capacité de travail, un status après fracture oblique de l'annulaire droit en 1992, un status après suture du long fléchisseur du pouce droit en 1982 et un diabète de type II. Le médecin a attesté d'une incapacité totale de travail depuis le 18 octobre 2000 et a retenu les limitations fonctionnelles suivantes: travail en position assise uniquement, sans marche, sans port de charges, sans montée ou descente d'escaliers, d'échafaudage ou d'échelles. Il a également estimé que les capacités de concentration, de compréhension et d'adaptation ainsi que la résistance, étaient limitées (rapport du 24 juin 2008). Le docteur P._ a fait état d'une aggravation de l'état de santé (rapport du 2 octobre 2008).
Le docteur O._, médecin au SMR, a admis que la capacité de travail de S._ était entière dans une activité ne nécessitant pas de station debout, de déplacements sur des longues distances ou sur sol irrégulier, le port de charges et le travail au-dessus de l'horizontal ou en porte-à-faux avec le membre supérieur droit (rapport du 20 octobre 2008).
Dans un projet de décision du 23 octobre 2008, l'office AI a refusé l'octroi de toute prestation. S._ a contesté la manière de voir de l'office AI et a produit un rapport médical du docteur A._, psychiatre traitant, qui a diagnostiqué une évolution dépressive torpide, désormais chronique et qui a signalé l'évidence de tendances de type hypocondriaque. Ce médecin a estimé que la capacité de travail de l'assuré était nulle du point de vue psychiatrique depuis de nombreuses années, au moins depuis l'apparition de l'algoneurodystrophie (rapport du 12 février 2009).
A la suite de cet avis psychiatrique, l'office AI a confié un mandat d'expertise au docteur L._, psychiatre au Centre d'expertise médicale (CEMed). Dans son rapport du 9 novembre 2009, le docteur L._ a diagnostiqué avec répercussion sur la capacité de travail, un trouble de la personnalité mixte (F 61.0 selon CIM-10) et, sans répercussion sur la capacité de travail, un trouble douloureux somatoforme (F 45.0 selon CIM-10) et un épisode dépressif léger sans syndrome somatique (F 32.00). Pour l'expert, le trouble de la personnalité entraînait des limitations sur le plan relationnel car les contacts étaient difficiles à gérer du fait qu'ils étaient vécus sur un mode paranoïaque. Ils devaient donc être limités, tout comme le stress et les exigences professionnelles pour éviter de mettre l'assuré sous pression et ainsi déclencher un vécu persécutoire plus important. Moyennant le respect de ces limitations, l'activité antérieure et toute autre activité étaient exigibles à 100 %.
Dans deux rapports des 2 et 16 février 2010, le docteur I._, médecin au SMR, a diagnostiqué un trouble de la personnalité mixte ainsi qu'un status après entorse de Lisfranc et fracture de la base du 1er métatarsien. Il a retenu une capacité totale de travail dans une activité respectant les limitations fonctionnelles déterminées par les docteurs O._ et L._.
Le 1er juin 2010, l'office AI a soumis à l'assuré un nouveau projet de décision, annulant et remplaçant celui du 23 octobre 2008, par lequel il envisageait de refuser toute prestation de l'assurance-invalidité, dès lors que le taux d'invalidité était de 28 %. Par décision du 25 janvier 2011, l'office AI a confirmé son refus de rente; par lettre du même jour, il a proposé une aide au placement.
B.
S._ a déféré cette décision au Tribunal cantonal du canton de Vaud, Cour des assurances sociales, en demandant son annulation. Il a conclu principalement au renvoi de la cause à l'office AI, subsidiairement à l'octroi d'une rente entière à compter du 1 er mai 2007, fondée sur un taux d'invalidité de 70 %.
Par jugement du 21 septembre 2012, la juridiction cantonale a rejeté le recours.
C.
S._ interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation, sous suite de frais et dépens, en concluant principalement à l'octroi d'une rente entière de l'assurance-invalidité dès le 1er décembre 2008, subsidiairement au renvoi de l'affaire à la juridiction cantonale pour expertise pluridisciplinaire. Il sollicite le bénéfice de l'assistance judiciaire.

Considérant en droit:
1.
1.1. Le recours en matière de droit public (<ref-law>) peut être formé pour violation du droit selon les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours ni par la motivation retenue par l'autorité précédente ; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (cf. <ref-ruling> consid. 1.4 p. 140).
1.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il peut cependant rectifier ou compléter d'office les constatations de l'autorité précédente si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>).
2.
Le litige porte sur le droit du recourant à une rente de l'assurance-invalidité. A cet égard, le jugement cantonal expose correctement les règles légales et la jurisprudence relatives au droit applicable, aux conditions d'octroi d'une rente et à son évaluation ainsi qu'à la valeur probante des rapports médicaux. Il suffit d'y renvoyer.
3.
En ce qui concerne le volet psychiatrique, la juridiction cantonale a reconnu pleine valeur probante à l'expertise du docteur L._, faisant ainsi sienne l'appréciation de la capacité de travail du recourant et des limitations fonctionnelles qui y sont retenues.
Sur le plan somatique, elle s'est référée à l'avis de la doctoresse V._, qui a admis, du point de vue rhumatologique, une absence d'atteinte organique du membre supérieur droit suffisamment importante pour justifier une limitation de la capacité de travail en tant qu'ouvrier polyvalent. Concernant le pied droit, la juridiction cantonale s'est également fondée sur l'avis de la doctoresse V._, qui avait, en mars 2001, reconnu que cette atteinte autorisait un travail à 50 % à l'époque de l'examen, avec une augmentation ultérieure à 75 voire 100 %. L'algoneurodystrophie ayant disparu, la juridiction cantonale a fait sien l'avis du docteur O._ pour qui la capacité de travail sur le plan somatique est entière moyennant le respect des limitations fonctionnelles déterminées. Ainsi, elle a retenu une capacité de travail entière dans une activité adaptée.
4.
4.1. Le recourant reproche à la juridiction cantonale d'avoir apprécié les preuves de façon arbitraire et d'avoir violé l'art. 61 let. c LPGA, en accordant pleine valeur probante à l'expertise du docteur L._, dont il prétend qu'elle contient des contradictions et qu'elle ne répond pas suffisamment aux arguments avancés par le docteur A._.
Lorsque l'autorité cantonale juge l'expertise concluante et en fait sien le résultat, le Tribunal fédéral n'admet le grief d'appréciation arbitraire que si l'expert n'a pas répondu aux questions posées, si ses conclusions sont contradictoires ou si, d'une quelconque autre façon, l'expertise est entachée de défauts à ce point évidents et reconnaissables, même sans connaissances spécifiques, que le juge ne pouvait tout simplement pas les ignorer. Il n'appartient pas au Tribunal fédéral de vérifier si toutes les affirmations de l'expert sont exemptes d'arbitraire; sa tâche se limite bien plutôt à examiner si l'autorité intimée pouvait, sans arbitraire, se rallier au résultat de l'expertise (arrêt 9C_997/2012 du 10 avril 2013 consid. 2.3).
4.2. Par ailleurs, le recourant conteste la manière dont l'expertise a été réalisée. Il soutient qu'elle a consisté en une simple observation d'une heure sans autres examens.
Aucun argument ne peut toutefois être tiré de la durée de l'examen. S'agissant de l'absence d'autres examens - allusion au fait que l'expert n'a procédé à aucun test projectif -, il faut relever que le docteur L._ a expliqué que ce genre de tests pouvaient être considérés comme utiles dans l'aide diagnostique, mais qu'ils n'avaient pas de valeur prépondérante par rapport à l'examen clinique. Dans le cas du recourant, l'expert a précisé qu'il n'avait pas retrouvé lors de son examen les critères cliniques de la structure psychotique et que les troubles de la personnalité signalés par le docteur A._ étaient plutôt des traits de personnalité. L'expert a exposé de façon claire les motifs pour lesquels il s'était écarté du diagnostic de structure psychotique retenue par le docteur A._. Les critiques du recourant sur ce point ne sont donc pas pertinentes.
4.3. Le recourant estime que l'expertise du docteur L._ contient des éléments contradictoires car l'expert a d'abord mentionné un épisode dépressif moyen sans syndrome somatique puis a retenu, sans explication, l'existence d'une dépression légère.
Cette critique du recourant relève d'une lecture évasive de l'expertise. En effet, l'expert a commencé par préciser que l'anamnèse permettait "d'évoquer un diagnostic d'épisode dépressif moyen sans syndrome somatique et des traits paranoïaques et obsessionnels". Puis, après avoir procédé à ses observations personnelles, l'expert a considéré que l'examen objectif mettait en évidence un comportement douloureux, des signes dépressifs d'intensité légère, des traits paranoïaques, obsessionnels et narcissiques. Il n'y a donc aucune contradiction dans l'expertise, le docteur L._ ayant uniquement expliqué une différence entre l'anamnèse et ses constatations personnelles.
4.4. Quant au diagnostic de trouble somatoforme douloureux, retenu par l'expert et nié par le docteur A._, il faut relever que son existence n'a pas d'incidence sur le sort de l'affaire puisque l'expert a retenu que cette atteinte n'avait pas de répercussion sur la capacité de travail.
5.
En ce qui concerne les troubles somatiques, le recourant reproche à la juridiction cantonale de s'être fondée sur l'avis de la doctoresse V._, rédigé plus de sept ans avant le dépôt de la demande de prestations de l'AI, alors que son état de santé avait évolué de façon défavorable depuis cette époque. Il voit dans le fait de ne pas avoir tenu compte des avis des docteurs C._ et F._ une violation du principe de la libre appréciation des preuves.
Ce point de vue ne saurait être suivi. En effet, les conclusions de la doctoresse Verraguth (rapport du 4 mars 2001) faisaient état d'atteintes à la santé plus nombreuses que celui du docteur P._ (rapport du 24 juin 2008). Celui-ci n'a mentionné en plus que le diabète de type II, diagnostiqué par le docteur F._ (rapport du 19 décembre 2007). Il faut donc en déduire que certaines affections avaient disparu entre-temps, mais que pour l'essentiel il n'y avait pas eu de changement. De plus, il faut retenir que le docteur P._ a considéré que le diabète de type II était sans répercussion sur la capacité de travail de l'assuré. Quant au rapport du docteur C._ (du 19 novembre 2007), qui fait état d'une insuffisance artérielle bilatérale des membres inférieurs avec artériopathie occlusive touchant principalement l'étage fémoral, il a été remis au docteur P._ qui n'a pas jugé utile de reprendre cette affection dans ses conclusions. Au vu de ces éléments, il apparaît que la juridiction cantonale pouvait se baser sur le rapport de la doctoresse V._ vu l'absence de changements importants dans l'état de santé de l'assuré entre le moment de l'établissement de ce rapport et la décision de l'office AI.
6.
Il résulte du dossier que les arguments du recourant, invoqués à l'encontre de la prise en compte de l'expertise du docteur L._ et du rapport de la doctoresse V._, ne sont pas de nature à mettre en doute ces rapports et qu'en conséquence, la juridiction cantonale pouvait les retenir, sans faire preuve d'arbitraire ni violer le droit.
S'agissant de la demande d'expertise déposée en procédure cantonale par le recourant, il faut admettre, au vu des éléments médicaux du dossier, que la juridiction cantonale pouvait y renoncer dans le cadre d'une appréciation anticipée des preuves sans violer le droit du recourant d'être entendu.
7.
7.1. Le recourant critique la manière dont la juridiction cantonale a procédé à la comparaison des revenus, avec et sans invalidité. Il soutient que la fixation du taux d'invalidité à 37 %, soit en-dessous du seuil de 40 % ouvrant droit à la rente, résulte de la prise en compte à tort, à titre de revenu sans invalidité, du salaire réalisé en 1999 et actualisé en 2001. Selon le recourant, les premiers juges auraient dû comparer les revenus en 2008, soit au moment de la naissance du droit à la rente ou en 2011, au moment de la décision. Par cette erreur, les augmentations de salaire auxquelles il aurait eu droit jusqu'en 2011, suivant les règles applicables aux salaires prévus pour les fonctionnaires de X._ à Z._, lesquelles dépassent le renchérissement, n'ont pas été prises en compte. La correction devrait ainsi aboutir à un taux d'invalidité de 40 % au moins.
7.2. Pour procéder à la comparaison des revenus, il convient de se placer au moment de la naissance du droit à la rente; les revenus avec et sans invalidité doivent être déterminés par rapport à un même moment et les modifications de ces revenus susceptibles d'influencer le droit à la rente survenues jusqu'au moment où la décision est rendue être prises en compte (<ref-ruling> consid. 4.1 et les références). Si les premiers juges ont admis à juste titre que la comparaison des revenus aurait être dû établie en fonction de la situation existant en 2008, ils ont toutefois considéré que cette erreur n'avait pas eu d'incidence sur le résultat final, dès lors que le taux d'invalidité restait inférieur à 40 %.
En ce qui concerne le revenu sans invalidité, le recourant n'apporte pas la moindre preuve que son salaire aurait augmenté davantage que le renchérissement entre 1999 et 2008 respectivement 2011, à un point tel que la comparaison des revenus puisse alors aboutir à un degré d'invalidité de 40 % au moins. Au surplus, le recourant ne conteste pas l'exactitude du calcul du taux d'invalidité en tant que tel, ni le fait que la simple indexation des revenus jusqu'en 2008 puisse conduire à un résultat différent. Dès lors que les faits n'ont pas été établis de façon manifestement inexacte ou en violation du droit (<ref-law>), le Tribunal fédéral est lié par ceux-ci (<ref-law>). Le recours est ainsi infondé.
8.
Le recourant voit ses conclusions rejetées, de sorte qu'il doit en principe supporter les frais de justice et ses propres dépens (art. 66 al. 1 et 68 al. 1 LTF). Dès lors que les conditions mises à son octroi sont remplies (art. 64 al. 1 et 2 LTF), il convient d'accorder au recourant l'assistance judiciaire qu'il a sollicitée. Le recourant est toutefois rendu attentif au fait qu'il devra rembourser la caisse du Tribunal s'il se trouve ultérieurement en mesure de le faire (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
L'assistance judiciaire est accordée au recourant.
3.
Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant. Ils sont toutefois supportés provisoirement par la caisse du Tribunal.
4.
M e Jean-Michel Duc est désigné en tant qu'avocat d'office du recourant et une indemnité de 2'800 fr. lui est allouée à titre d'honoraires, supportée par la caisse du Tribunal.
5.
Le présent arrêt est communiqué aux parties, au Tribunal cantonal du canton de Vaud, Cour des assurances sociales, et à l'Office fédéral des assurances sociales.
Lucerne, le 7 août 2013
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: Kernen
Le Greffier: Berthoud