Faits: A. A.a. X._, né en 1959, d'origine algérienne, naturalisé suisse en 1998, a obtenu un diplôme algérien de docteur en médecine en septembre 1983. Il est également titulaire d'une "attestation d'études spéciales relatives aux applications à la biologie médicale des radio-éléments artificiels" (ci-après: AES) et d'un "certificat d'études spéciales relatives aux applications à la médecine des radio-éléments artificiels" (ci-après: CES) datés du 25 mai 1992 et attestant sa réussite aux examens finaux, auprès de l'Université de Paris XII, en date du 12 juillet 1985, respectivement du 9 octobre 1986. Le 19 juillet 1987, le Ministère algérien de l'enseignement supérieur lui a délivré une attestation d'équivalence de ses deux titres français avec le diplôme algérien d'études médicales spéciales de médecine nucléaire (ci-après: DEMS). A.b. Par arrêté du 4 février 1997, le Conseil d'Etat du canton de Fribourg a délivré à X._ une autorisation spéciale de pratiquer la médecine sur le territoire cantonal pour une durée de trois ans. Celui-ci a exercé, au sein du laboratoire A._, la fonction de médecin responsable de l'unité de médecine nucléaire, spécialiste de la scintigraphie du coeur et des artères coronaires, jusqu'alors inexistante dans le canton de Fribourg. Par arrêté du 17 août 1999, le Conseil d'Etat a reconduit jusqu'au 31 décembre 2001 l'autorisation spéciale d'exercer la médecine au sein de A._ uniquement. Cette autorisation a été renouvelée avec effet jusqu'au 31 décembre 2003. Le 23 décembre 2002, X._ a requis l'ancien Comité directeur des examens fédéraux pour les professions médicales de reconnaître son diplôme de docteur en médecine délivré à Alger et l'ancien Comité de la formation postgrade pour les professions médicales de reconnaître son CES. Ces demandes ont été rejetées par décisions des 24 mars et 15 avril 2004, confirmées sur recours par l'ancienne Commission fédérale de recours pour la formation de base et la formation postgrade des professions médicales, puis par arrêt du Tribunal fédéral du 13 janvier 2006 dans les causes jointes 2A.157/2005 et 2A.195/2005 (ATF 132 II 135). Entre-temps, le 9 février 2004, la Direction de la santé et des affaires sociales du canton de Fribourg a délivré à X._ une autorisation de pratiquer la médecine exclusivement auprès de la société B._, pour une période limitée au 31 décembre 2004, les conditions de l'autorisation du 17 août 1999 étant réservées. Elle a en outre précisé que cette autorisation pourrait être prolongée si, à l'échéance, une procédure de recours relative à la reconnaissance de son diplôme de médecin était pendante devant le Tribunal fédéral. Cette décision a été confirmée par le Tribunal administratif du canton de Fribourg, puis par le Tribunal fédéral (arrêt du 29 mars 2007 dans les causes jointes 2P.268/2006 et 2A.615/2006). A.c. Le 28 juin 2007, X._ a déposé auprès du Service de la santé publique du canton de Fribourg (ci-après: le Service de la santé publique) une demande d'autorisation exceptionnelle d'exercer la médecine à titre indépendant, fondée sur l'art. 36 al. 3 let. b de la loi fédérale du 23 juin 2006 sur les professions médicales universitaires (LPMéd, RS 811.11), dont l'entrée en vigueur était prévue pour le 1 er septembre 2007. Par courrier du 13 décembre 2007, le Service de la santé publique a précisé à l'intéressé qu'il entrerait en matière sur sa demande, si l'équivalence de sa formation pouvait être établie. Le 4 mars 2008, X._ a déposé auprès de la Commission des professions médicales ("Medizinalberufekommission", en abrégé MEBEKO) une demande d'attestation d'équivalence de diplôme et de titre postgrade étrangers, au sens de l'art. 36 al. 3 LPMéd. Par lettre du 9 mai 2008, il a précisé qu'il requérait également que soit reconnue l'équivalence de son "diplôme français de spécialiste en médecine nucléaire" avec le titre postgrade fédéral relatif à la médecine nucléaire. Par décision du 17 juin 2009, la Commission des professions médicales, section "formation universitaire", a retenu que le diplôme algérien de docteur en médecine du requérant était équivalent au diplôme fédéral. Le 15 décembre 2009, elle lui a délivré une attestation d'équivalence. B. B.a. Le 16 juillet 2009, la Commission des professions médicales, section "formation postgrade", s'est saisie de la demande de X._ en tant qu'elle portait sur l'attestation d'équivalence d'un titre postgrade étranger. Elle a invité l'intéressé à fournir la preuve qu'il avait suivi avec succès une formation postgrade en médecine nucléaire dans un Etat avec lequel la Suisse n'avait pas conclu d'accord de reconnaissance mutuelle. Le 23 mars 2010, X._ a exposé, en substance, qu'il maintenait sa demande d'attestation d'équivalence avec le titre postgrade fédéral de spécialiste en médecine nucléaire tant pour ses CES et AES que pour l'attestation algérienne d'équivalence avec le DEMS du 19 juillet 1987. Il a en outre produit une copie certifiée conforme d'une attestation établie le 17 février 2010 par la Direction algérienne des services de santé - laquelle y confirme que l'attestation du "18 juillet 1985" (soit du 19 juillet 1987 selon X._) lui donne le droit d'exercer sa spécialité dans les structures médicales algériennes -, ainsi que d'une attestation établie le 18 janvier 2010 par le président du Comité pédagogique national de médecine nucléaire, à Alger. Il ressort de ce dernier document que le DEMS est "un diplôme de spécialité médicale obtenu par des médecins ayant suivi régulièrement les quatre ans d'études de la spécialité médecine nucléaire et ayant subi avec succès l'examen national final" et que ce diplôme "permet à tout titulaire du doctorat en médecine d'exercer la médecine nucléaire en Algérie dans le cadre réglementaire régissant l'exercice des spécialités médicales ". B.b. Par décision du 10 janvier 2011, la Commission des professions médicales, section "formation postgrade", a rejeté la demande de X._ en tant qu'elle portait sur l'attestation d'équivalence d'un titre postgrade étranger. Elle a retenu que les trois attestations algériennes produites - soit l'attestation d'équivalence du CES et de l'AES avec le DEMS du 19 juillet 1987, l'attestation du 18 janvier 2010, ainsi que celle du 17 février 2010 - n'étaient pas propres à prouver que l'intéressé avait obtenu un titre postgrade en Algérie. Faute d'avoir présenté un titre postgrade étranger obtenu dans un Etat avec lequel la Suisse n'a pas conclu de traité de reconnaissance réciproque, X._ ne pouvait se voir octroyer l'équivalence demandée. C. Le 10 février 2011, X._ a interjeté recours contre cette décision auprès du Tribunal administratif fédéral. Par courriers des 21 et 27 juin 2011, X._ a produit une copie certifiée conforme d'une écriture du Conseil national de l'Ordre des médecins français du 6 mai 2011, dans laquelle le président de la section "formation et compétences médicales" et la présidente de la Commission nationale de première instance de qualification en médecine nucléaire attestent que "les Certificats d'Etudes Spéciales relatifs aux applications à la Biologie et à la Médecine des radios-éléments artificiels obtenus en 1992, à Créteil, donnent bien droit à la qualification de Médecin spécialiste en Médecine Nucléaire et représentent l'équivalent à l'actuel DES en Médecine Nucléaire ". Il a relevé que ce document émanait de l'autorité qui avait émis la décision du 16 janvier 1997, sur la base de laquelle sa soeur avait obtenu la reconnaissance en Suisse de son titre de spécialiste. Par arrêt du 23 mai 2012, le Tribunal administratif fédéral a rejeté le recours. D. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du 23 mai 2012 et, principalement, de renvoyer le dossier de la cause à la Commission des professions médicales pour nouvelle décision dans le sens des considérants; subsidiairement, il conclut à ce que le dossier soit renvoyé à la Commission des professions médicales "pour nouvelle décision au sens des considérants sur l'équivalence de l'attestation algérienne du 19 juillet 1987" et à ce que ses diplômes français CES et AES soient considérés comme équivalents au titre postgrade fédéral de médecin spécialiste en radiologie médicale/médecine nucléaire, la commission prénommée étant invitée à lui délivrer une attestation correspondante. Le Tribunal administratif fédéral renonce à se déterminer sur le recours. La Commission des professions médicales, section "formation postgrade", conclut à son rejet. Le Département fédéral de l'intérieur se rallie aux considérants de l'arrêt attaqué.