Faits : A. A._, ressortissant étranger, est arrivé en Suisse en mai 1999 et y a obtenu une autorisation de séjour. Il a travaillé en qualité de garçon d'office pour le compte de l'Hôtel C._ SA du 1 er juin 2000 au 14 mars 2011. Le 15 avril 2013, il a déposé une demande de prestations de l'assurance-invalidité (AI). Dans un rapport du 17 juin 2013, la doctoresse D._, médecin assistante auprès du Département de psychiatrie du Centre Hospitalier E._ a attesté que le patient présentait une incapacité de travail depuis l'enfance, en raison d'un retard mental léger à moyen (F.70). Par décision du 12 mai 2014, l'Office de l'assurance-invalidité pour le canton de Vaud (ci-après: l'office AI) a nié le droit de A._ à une rente et à des mesures d'ordre professionnel, motifs pris que malgré le retard mental léger à moyen dont il souffrait depuis l'enfance, il avait pu travailler pendant plus de dix ans à satisfaction de son employeur. Le taux d'invalidité a été fixé à 35 %; l'office AI a précisé que des mesures professionnelles ne permettraient pas de diminuer le préjudice économique. B. A._ a déféré cette décision au Tribunal cantonal du canton de Vaud, Cour des assurances sociales, en concluant à la reconnaissance de son droit à une rente entière d'invalidité, subsidiairement à la mise en oeuvre d'un stage "COPAI" ou à une expertise judiciaire. La juridiction cantonale a invité les parties à se déterminer sur une éventuelle substitution de motifs, car la question des conditions d'assurance se posait en l'état. A._ a dès lors complété ses conclusions, demandant principalement l'annulation de la décision du 12 mai 2014 et la reconnaissance de son droit à une rente entière d'invalidité, subsidiairement la mise en oeuvre d'une expertise judiciaire, plus subsidiairement la constatation de la réalisation des conditions de fond d'octroi d'une rente entière d'invalidité à compter du 1 er octobre 2013. Il s'est prévalu d'un intérêt actuel à obtenir un jugement en constatation portant sur les conditions de fond du droit à la rente d'invalidité, afin de pouvoir clarifier sa situation vis-à-vis d'autres prestataires sociaux. Par jugement du 14 mars 2016, le tribunal cantonal a rejeté le recours dans la mesure où il est recevable. Il a confirmé la décision du 12 mai 2014 par substitution de motifs. C. A._ interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation en tant qu'il déclare irrecevables ses conclusions constatatoires. A titre principal, il conclut à ce qu'il soit constaté qu'il remplit les conditions matérielles du droit à une rente entière d'invalidité; à titre subsidiaire, il conclut au renvoi de la cause à la juridiction cantonale pour qu'elle reprenne "l'instruction de l'invalidité". Il sollicite l'octroi de l'assistance judiciaire pour la procédure fédérale. L'office intimé conclut implicitement au rejet du recours. L'Office fédéral des assurances sociales a renoncé à se déterminer.