Faits: A. A.a. Ressortissant français né en 1970, X._ est arrivé en Suisse le 6 septembre 2004. Au bénéfice d'un contrat de travail signé le même jour avec la société Y._ Sàrl pour un emploi de vendeur à temps plein, X._ a obtenu une autorisation de séjour CE/AELE valable jusqu'au 30 septembre 2009. Selon une attestation du 26 novembre 2009 du Centre social de Z._, X._ a bénéficié du revenu minimum de réinsertion du 1 er octobre au 30 novembre 2005. Il percevait, en outre, le revenu d'insertion depuis le 1 er août 2008. Le montant total de ces prestations s'élevait alors à 47'690 fr. 80. A.b. Le 22 décembre 2009, le Service de la population du canton de Vaud (ci-après: le Service cantonal) a renouvelé l'autorisation de séjour de l'intéressé pour une année. Le Service cantonal a cependant précisé que cette autorisation de séjour pourrait être révoquée si l'intéressé ne retrouvait pas son autonomie financière à l'échéance du permis de séjour. Le 14 septembre 2010, X._ a sollicité la prolongation de son autorisation de séjour. Il a indiqué avoir engagé une procédure le 4 juin 2010 auprès de l'Office de l'assurance-invalidité du canton de Vaud (ci-après: l'Office AI) en vue d'envisager sa réinsertion professionnelle. Le 30 décembre 2010, le Service cantonal a à nouveau prolongé l'autorisation de séjour d'une année, dans l'attente de la décision de l'Office AI. Le Service cantonal a, en outre, invité X._ à produire la décision de l'Office AI à l'échéance de son autorisation de séjour et à se déterminer sur les circonstances de la survenance de l'événement ayant entraîné son incapacité de travail. Le 23 décembre 2011, X._ a formulé une nouvelle demande de prolongation de son autorisation de séjour. A.c. Sur demande du Service cantonal, X._ a produit, le 20 mars 2012, un projet de décision de l'Office AI daté du 1 er décembre 2011, d'où il ressortait que l'autorité envisageait de rejeter la demande de rente d'invalidité, au motif que l'incapacité de travail de l'intéressé n'était que de 20%. L'Office AI avait également informé l'intéressé de son intention de refuser de le mettre au bénéfice de mesures professionnelles. Le 22 mars 2012, faisant suite à une contestation de l'intéressé contre le projet de décision du 1 er décembre 2011, l'Office AI a accepté de mettre X._ au bénéfice d'une mesure d'orientation professionnelle. Dans un projet de décision du 30 mai 2012, l'Office AI a communiqué à l'intéressé un nouveau préavis de refus de reclassement et de rente d'invalidité. X._ a contesté ce projet de décision. B. Le 18 avril 2012, le Service cantonal a informé l'intéressé de son intention de refuser la prolongation de l'autorisation de séjour et lui a donné l'occasion de se déterminer, ce que l'intéressé a fait par courrier du 28 mai 2012. Par décision du 2 août 2012, le Service cantonal a refusé de prolonger l'autorisation de séjour de X._ et lui a imparti un délai de trois mois pour quitter la Suisse. Selon cette décision, l'intéressé avait bénéficié de prestations d'assistance pour un montant total de 104'964 francs. Par acte du 5 septembre 2012, X._ a formé recours contre la décision du 2 août 2012 auprès de la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal). Le 22 mai 2013, le Tribunal cantonal a rejeté le recours et confirmé la décision du 2 août 2012. Se fondant sur le taux d'invalidité retenu par l'Office AI, le Tribunal cantonal a notamment considéré que l'intéressé ne remplissait pas les conditions permettant de bénéficier du droit de demeurer en Suisse au sens de l'art. 4 annexe I de l'Accord du 21 juin 1999, entré en vigueur le 1 er juin 2002, entre la Confédération suisse, d'une part, et la Communauté européenne et ses États membres, d'autre part, sur la libre circulation des personnes (ci-après: ALCP; RS 0.142.112.681). C. X._ forme un " recours de droit public, subsidiairement un recours constitutionnel " contre le jugement rendu le 22 mai 2013 par le Tribunal cantonal. Il conclut à l'annulation de l'arrêt entrepris et à la reconnaissance de son droit au renouvellement de l'autorisation de séjour. Il sollicite l'octroi de l'assistance judiciaire. Par ordonnance du 8 août 2013, le Président de la IIe Cour de droit public a informé l'intéressé qu'il serait statué ultérieurement sur sa demande d'assistance judiciaire. Le Service cantonal renonce à se déterminer. Le Tribunal cantonal se réfère aux considérants de l'arrêt attaqué alors que l'Office fédéral des migrations conclut à son rejet. Le 14 octobre 2013, le recourant a fait parvenir au Tribunal fédéral un nouveau projet de décision de l'Office AI daté du 8 octobre 2013.