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.