Faits:
Faits:
A. A.a P._, de nationalité portugaise, a subi une luxation du coude droit en 1993. En raison des séquelles de cette blessure, il a dû cesser son activité de manoeuvre-maçon et a déposé une demande de prestations de l'assurance-invalidité. Par décision du 27 juin 1995, l'Office de l'assurance-invalidité du canton du Jura lui a alloué une rente entière, sur la base d'un taux d'invalidité de 80 %.
De son côté, la Caisse nationale suisse d'assurance en cas d'accidents (CNA) a fait examiner P._ à la Clinique X._, du 10 au 19 juillet 1995. Par décision du 25 avril 1996, elle lui a accordé une rente complémentaire fondée sur une incapacité de gain de 33 1/3 %.
A.b Par la suite, le prénommé est retourné s'établir au Portugal. En 1997, l'Office AI pour les assurés résidant à l'étranger (ci-après : l'Office AI) a ouvert une procédure de révision du droit à la rente. Par décision du 18 novembre 1998, il a supprimé la rente d'invalidité allouée précédemment, en considérant que P._ était à nouveau en mesure d'exercer une activité lucrative adaptée à son état de santé et pouvait réaliser plus de la moitié du gain qu'il aurait pu obtenir s'il n'était pas devenu invalide.
P._ a déféré la cause à la Commission fédérale de recours en matière d'assurance-vieillesse, survivants et invalidité pour les personnes résidant à l'étranger, puis, en dernière instance, au Tribunal fédéral des assurances. Par arrêt du 19 janvier 2001, ce dernier a confirmé la décision de suppression du droit à la rente. Il a considéré que l'état de santé de l'assuré ne s'était pas modifié entre le moment de l'octroi de la rente et celui de sa suppression par l'Office AI, contrairement à ce qu'avaient admis les instances précédentes, mais que la décision par laquelle cette prestation avait été allouée était manifestement erronée et que sa rectification revêtait une importance notable.
P._ a déféré la cause à la Commission fédérale de recours en matière d'assurance-vieillesse, survivants et invalidité pour les personnes résidant à l'étranger, puis, en dernière instance, au Tribunal fédéral des assurances. Par arrêt du 19 janvier 2001, ce dernier a confirmé la décision de suppression du droit à la rente. Il a considéré que l'état de santé de l'assuré ne s'était pas modifié entre le moment de l'octroi de la rente et celui de sa suppression par l'Office AI, contrairement à ce qu'avaient admis les instances précédentes, mais que la décision par laquelle cette prestation avait été allouée était manifestement erronée et que sa rectification revêtait une importance notable.
B. B.a Le 21 mai 2002, P._ a présenté une nouvelle demande de prestations de l'assurance-invalidité en alléguant une détérioration de son état de santé depuis la décision du 18 novembre 1998. A l'appui de sa demande, il présentait plusieurs rapports établi les 12 février et 23 juillet 2001 par le docteur C._, les 16 février et 27 juillet 2001 par le docteur D._, ainsi que le 26 mars 2003 par le docteur S._. Selon le Service médical de l'Office AI, toutefois, ces documents décrivaient un état de santé identique à celui de l'assuré en 1998 au moment de la décision de suppression de rente (prises de position des 22 mai et 21 juillet 2003 du docteur H._).
Par décision et décision sur opposition des 29 juillet et 29 octobre 2003, l'Office AI a rejeté la nouvelle demande de l'assuré.
B.b Ce dernier a déféré la cause à la Commission de recours en matière d'assurance-vieillesse, survivants et invalidité pour les personnes résidant à l'étranger (ci-après : la Commission), en produisant plusieurs rapports médicaux, notamment un rapport établi le 18 novembre 2003 à l'Hôpital Y._ (Portugal), ainsi qu'un rapport du 19 novembre 2003 du docteur D._.
Par jugement du 8 avril 2004, la Commission a rejeté le recours de l'assuré.
Par jugement du 8 avril 2004, la Commission a rejeté le recours de l'assuré.
C. Ce dernier interjette un recours de droit administratif contre ce jugement, dont il demande l'annulation. Il conclut, sous suite de frais et dépens, à l'octroi d'une rente entière d'invalidité et, à titre subsidiaire, au renvoi de la cause à l'Office AI pour complément d'instruction et nouvelle décision. A l'appui de son recours, il produit un rapport médical établi le 4 mai 2004 par le docteur D._.
L'Office AI produit une prise de position de son service médical (rapport du 6 juillet 2004 du docteur L.._) et conclut au rejet du recours, alors que l'Office fédéral des assurances sociales a renoncé à se déterminer.

Considérant en droit:
Considérant en droit:
1. 1.1 Le litige porte sur la nouvelle demande de rente d'invalidité présentée par le recourant. Il convient par conséquent d'examiner, dans la présente procédure, si un changement de circonstances - ou un changement du droit applicable - est survenu depuis cette dernière date et justifierait désormais l'octroi d'une rente d'invalidité au recourant (cf. <ref-ruling> consid. 2; 73 ss consid. 3; <ref-ruling> consid. 3a).
1.2 Dans ce contexte, il convient de préciser que l'entrée en vigueur de l'Accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ALCP), le 1er juin 2002, ainsi que celle de la Loi fédérale du 6 octobre 2000 sur la partie générale du droit des assurances sociales (LPGA), le 1er janvier 2003, n'ont pas entraîné, matériellement, de modification des règles relatives à la notion d'invalidité, à l'échelonnement des rentes selon le taux d'invalidité et à la manière d'évaluer ce taux (<ref-ruling>; en ce qui concerne l'ALCP: <ref-ruling> consid. 2.4). En revanche, l'<ref-law>, qui prévoit que les rentes correspondant à un taux d'invalidité inférieur à 50 % ne sont versées qu'aux assurés qui ont leur domicile et leur résidence habituelle en Suisse, n'est plus opposable, depuis le 1er juin 2002, aux ressortissants des états parties à l'ALCP résidant sur le territoire de l'un de ces états (art. 10 par. 1 du règlement no 1408/71). De même, l'application de la clause de résidence prévue par l'art. 12 al. 2 de la Convention de sécurité sociale conclue entre la Suisse et le Portugal le 11 septembre 1975 est suspendue depuis l'entrée en vigueur de l'ALCP (<ref-law>; <ref-ruling> sv. consid. 2.3).
1.3 La novelle du 21 mars 2003 modifiant la LAI (4ème révision), entrée en vigueur le 1er janvier 2004, n'est pas applicable à la présente procédure, dès lors que le Tribunal fédéral des assurances n'a pas à se prononcer sur les conséquences juridiques de faits survenus postérieurement à la décision sur opposition litigieuse (cf. <ref-ruling> consid. 1, 121 V 366 consid. 1b).
1.3 La novelle du 21 mars 2003 modifiant la LAI (4ème révision), entrée en vigueur le 1er janvier 2004, n'est pas applicable à la présente procédure, dès lors que le Tribunal fédéral des assurances n'a pas à se prononcer sur les conséquences juridiques de faits survenus postérieurement à la décision sur opposition litigieuse (cf. <ref-ruling> consid. 1, 121 V 366 consid. 1b).
2. 2.1 A l'appui de sa nouvelle demande, le recourant soutient que son état de santé s'est péjoré depuis la décision 18 novembre 1998 et qu'il s'en est suivi une augmentation de son taux d'invalidité. La dégradation alléguée de son état de santé serait établie par les différents rapports médicaux qu'il a produits devant les instances précédentes, ainsi qu'avec son recours de droit administratif.
2.2 Ce point de vue ne peut pas être suivi. La plupart des rapports cités font état, certes, d'une aggravation des douleurs ressenties par l'assuré et attestent une incapacité de travail totale. Mais, d'une part, les médecins consultés se réfèrent à la capacité de travail dans la profession exercée précédemment par le recourant, relativement lourde, et ne précisent pas dans quelle mesure l'exercice d'une activité plus légère serait possible. D'autre part, les docteurs H._ et L.._ ont comparé les résultats objectifs des examens décrits dans les documents auxquels se réfère l'assuré à ceux figurant dans un rapport établi le 14 décembre 1998 par le docteur C._. Or, ces résultats se sont avérés, pour l'essentiel, identiques; tout au plus permettent-ils d'admettre, en plus des atteintes déjà constatées, le développement de lombalgies sans répercussion sur la capacité de travail du recourant dans une activité légère (rapports du docteur H._ des 22 mai et 21 juillet 2003; rapports du docteur L.._ des 10 janvier et 6 juillet 2004). Dans la mesure où le jugement entrepris se fonde sur ces constatations pour nier un changement de circonstances justifiant désormais l'octroi d'une rente d'invalidité au recourant, il n'est pas critiquable.
2.2 Ce point de vue ne peut pas être suivi. La plupart des rapports cités font état, certes, d'une aggravation des douleurs ressenties par l'assuré et attestent une incapacité de travail totale. Mais, d'une part, les médecins consultés se réfèrent à la capacité de travail dans la profession exercée précédemment par le recourant, relativement lourde, et ne précisent pas dans quelle mesure l'exercice d'une activité plus légère serait possible. D'autre part, les docteurs H._ et L.._ ont comparé les résultats objectifs des examens décrits dans les documents auxquels se réfère l'assuré à ceux figurant dans un rapport établi le 14 décembre 1998 par le docteur C._. Or, ces résultats se sont avérés, pour l'essentiel, identiques; tout au plus permettent-ils d'admettre, en plus des atteintes déjà constatées, le développement de lombalgies sans répercussion sur la capacité de travail du recourant dans une activité légère (rapports du docteur H._ des 22 mai et 21 juillet 2003; rapports du docteur L.._ des 10 janvier et 6 juillet 2004). Dans la mesure où le jugement entrepris se fonde sur ces constatations pour nier un changement de circonstances justifiant désormais l'octroi d'une rente d'invalidité au recourant, il n'est pas critiquable.
3. 3.1 Nonobstant ce qui précède, il convient encore d'examiner si le recourant peut prétendre l'octroi d'un quart de rente de l'assurance-invalidité depuis le 1er juin 2002, compte tenu de l'entrée en vigueur de l'ALCP. Dans l'arrêt du 19 janvier 2001, en effet, le Tribunal fédéral des assurances a implicitement admis que le taux d'invalidité présenté par le recourant était inférieur à 50 %, mais n'a pas précisé si un taux de 40 % ouvrant droit à un quart de rente - non exportable à l'époque (cf. consid. 1.2 supra) - entrait en considération.
3. 3.1 Nonobstant ce qui précède, il convient encore d'examiner si le recourant peut prétendre l'octroi d'un quart de rente de l'assurance-invalidité depuis le 1er juin 2002, compte tenu de l'entrée en vigueur de l'ALCP. Dans l'arrêt du 19 janvier 2001, en effet, le Tribunal fédéral des assurances a implicitement admis que le taux d'invalidité présenté par le recourant était inférieur à 50 %, mais n'a pas précisé si un taux de 40 % ouvrant droit à un quart de rente - non exportable à l'époque (cf. consid. 1.2 supra) - entrait en considération.
3.2 3.2.1 Au moment de la décision de suppression de rente du 18 novembre 1998, le recourant disposait, comme aujourd'hui, d'une pleine capacité résiduelle de travail dans une activité n'impliquant pas de gros effort du bras droit (pas de charge supérieure à 5 kg), ni l'utilisation trop répétitive de ce bras (rapports du 5 septembre 1995 du docteur O._, du 26 février 1999 de la doctoresse E._ et des 26 septembre 2003, 10 janvier et 6 juillet 2004 du docteur L.._). Le docteur L.._ en déduit une perte de rendement de 30 % dans les travaux industriels.
Le recourant n'ayant pas repris d'activité professionnelle, malgré cette capacité de travail, il convient d'évaluer sa capacité résiduelle de gain en se référant aux données salariales publiées par l'Office fédéral de la statistique (cf. <ref-ruling>). Il en ressort un salaire mensuel brut (valeur centrale) de 4'268 fr. pour les hommes exerçant une activité simple et répétitive en 1998 dans le secteur privé (Enquête suisse sur la structure des salaires 1998, tableau TA 1, p. 25). Ce revenu statistique tient compte d'un large éventail d'activités existant sur le marché du travail, dont on peut admettre qu'un nombre significatif d'entre elles sont adaptées aux aptitudes du recourant, sans perte de rendement, malgré les réserves émises par le docteur L.._ pour les activités industrielles. Comme les salaires bruts standardisés tiennent compte d'un horaire de travail de 40 heures, soit une durée inférieure à la moyenne hebdomadaire dans les entreprises en 1998 (41,9 heures: La Vie économique 10/2004, p. 90, tableau B 9.2), il convient de rectifier le revenu mentionné ci-dessus et de le porter à 4'471 fr. (4'268 fr. / 40 h. x 41.9 h.). Or, même en procédant à un abattement supplémentaire de 25 % - soit le taux maximum admis par la jurisprudence (cf. <ref-ruling> ss consid. 5) - pour tenir compte de l'ensemble des circonstances liées à la personne du recourant et de nature à limiter ses perspectives salariales, on parvient à une capacité résiduelle de gain de 3'353 fr. (4'471 fr. - 1'118 fr.), qui limite le taux d'invalidité du recourant à 32 % et exclut le droit à un quart de rente de l'assurance-invalidité. En ce qui concerne le revenu sans invalidité, en effet, P._ allègue un salaire de 4658 fr. par mois en 1993, soit 4'896 fr. en 1998, compte tenu de l'évolution de l'indice des salaires nominaux (1743 points en 1993 et 1832 points en 1998, pour les hommes : La Vie économique 12/1999, p. 28, tableau B10.3); rien au dossier n'indique que ce revenu aurait été plus élevé en réalité.
3.2.2 Vu ce qui précède, le recours est mal fondé, sans qu'il soit nécessaire d'examiner si un revenu sans invalidité inférieur à celui allégué par l'assuré devrait être pris en considération, comme l'ont admis les premiers juges.

Par ces motifs, le Tribunal fédéral des assurances prononce:
Par ces motifs, le Tribunal fédéral des assurances prononce:
1. Le recours est rejeté.
1. Le recours est rejeté.
2. Il n'est pas perçu de frais de justice ni alloué de dépens.
2. Il n'est pas perçu de frais de justice ni alloué de dépens.
3. Le présent arrêt sera communiqué aux parties, à la Commission fédérale de recours en matière d'AVS/AI pour les personnes résidant à l'étranger et à l'Office fédéral des assurances sociales.
Lucerne, le 28 juillet 2005
Au nom du Tribunal fédéral des assurances
Le Président de la IVe Chambre: Le Greffier: