Faits: A. Le 9 mai 2011, le Conseil de l'Union européenne (ci-après: le Conseil) a adopté la décision 2011/273/PESC concernant des mesures restrictives à l'encontre de la Syrie (JO 2011 L 121 du 10 mai 2011 p. 11). Cette décision institue notamment une interdiction d'entrée et de transit sur le territoire de l'Union pour les personnes mentionnées dans une annexe (art. 3 par. 1) et le gel de tous les fonds et ressources économiques appartenant à l'ensemble des personnes physiques ou morales, des entités et des organismes énumérés dans cette annexe (art. 4 par. 1; voir également règlement [UE] no 442/2011 du Conseil du 9 mai 2011 concernant des mesures restrictives en raison de la situation en Syrie [JO 2011 L 121 du 10 mai 2011 p. 1]). B. Le 18 mai 2011, le Conseil fédéral suisse a édicté l'ordonnance instituant des mesures à l'encontre de la Syrie (RO 2011 2193; ci-après: aO-Syrie). Ces mesures de coercition comprenaient notamment le gel des avoirs et des ressources économiques appartenant à ou sous contrôle des personnes physiques, entreprises et entités mentionnées dans l'annexe 2 (art. 2 al. 1 aO-Syrie), ainsi que, pour les personnes physiques citées dans dite annexe, une interdiction d'entrée en Suisse et de transit par la Suisse (art. 4 al. 1 aO-Syrie). L'annexe 2 mentionnait en 5ème position Hafez Makhlouf, avec les informations d'identification "né le 2.4.1971 à Damas; passeport diplomatique no 2246" et les indications suivantes sous la rubrique "Fonction resp. motifs": "Colonel dirigeant une unité au sein des renseignements généraux (General Intelligence Directorate Damascus Branch); proche de Maher Al-Assad; implication dans la répression contre les manifestants." L'annexe 2 a été modifiée à plusieurs reprises par le Département fédéral de l'économie - devenu entre-temps le Département fédéral de l'économie, de la formation et de la recherche (ci-après: le Département) -, la première fois le 24 mai 2011 (RO 2011 2285) et la dernière le 4 juin 2012 (RO 2012 3257). Dans sa nouvelle teneur du 24 mai 2011, l'annexe 2 mentionnait en 6ème position "Hafiz Makhluf (ou Hafez Makhlouf)", avec les mêmes informations d'identification et les indications suivantes sous la rubrique "Fonction resp. motifs": "Colonel dirigeant l'unité de Damas au sein de la direction des renseignements généraux; cousin du président Bashar Al-Assad; proche de Mahir Al-Assad; impliqué dans la répression contre les manifestants." C. Par acte du 17 juin 2011, Hafez Makhlouf a recouru au Tribunal administratif fédéral contre l'aO-Syrie, telle qu'amendée par la modification du 24 mai 2011. Il a conclu à l'annulation de ladite ordonnance dans la mesure où elle le concernait, au retrait de son nom et à la levée de toutes les mesures de blocage prises à son encontre sur ses avoirs en Suisse. Par courriers des 16 et 31 août 2011, la Cour III du Tribunal administratif fédéral et la Ière Cour de droit public du Tribunal fédéral ont procédé à un échange de vues sur la question de l'autorité compétente pour se saisir du recours. D. Arguant de l'effet suspensif de son recours, Hafez Makhlouf a requis, par écriture du 6 septembre 2011, de l'Office fédéral des migrations qu'il confirme qu'il était admis à entrer en Suisse afin, notamment, de s'entretenir avec son avocat. Ce courrier a été transmis au Tribunal administratif fédéral, lequel a, par décision du 14 septembre 2011, retiré l'effet suspensif du recours. Le recours interjeté par Hafez Makhlouf contre ce prononcé a été déclaré irrecevable par arrêt de la IIe Cour de droit public du Tribunal fédéral du 15 décembre 2011 (cause 2C_838/2011). E. Entre-temps, le 18 octobre 2011, le traitement du recours interjeté le 17 juin 2011 a été repris par la Cour II du Tribunal administratif fédéral. Le 8 juin 2012, le Conseil fédéral a édicté une nouvelle ordonnance instituant des mesures à l'encontre de la Syrie (RS 946.231.172.7; ci-après: O-Syrie). Celle-ci est entrée en vigueur le lendemain, en abrogeant celle du 18 mai 2011. Elle prévoit des mesures similaires à celles de la précédente, à l'encontre des personnes mentionnées dans une annexe 7, où figure Hafez Makhlouf. Par arrêt du 14 juin 2012, le Tribunal administratif fédéral est entré en matière sur le recours de Hafez Makhlouf et l'a rejeté. Sur le plan de la recevabilité, il a considéré que Hafez Makhlouf contestait son inscription respectivement dans l'annexe 2 de l'aO-Syrie et dans l'annexe 7 de l'O-Syrie. Bien qu'elle ait été effectuée dans l'annexe d'une ordonnance du Conseil fédéral, cette inscription avait pour effet de soumettre l'intéressé à des mesures de coercition (gel de ses avoirs, interdiction d'entrée et de transit sur territoire suisse) suffisamment individualisées et concrétisées pour qu'elle présente les caractéristiques matérielles d'une décision au sens de l'art. 5 de la loi fédérale du 20 décembre 1968 sur la procédure administrative (PA; RS 172.021). Sur le fond, les juges ont considéré que les restrictions des droits fondamentaux liées aux mesures de coercition en cause respectaient les conditions de l'art. 36 Cst. Sur le plan des faits, ils ont retenu qu'il existait "un large faisceau d'indices qui confine à la certitude" que Hafez Makhlouf jouait un rôle actif dans la répression de l'opposition au régime syrien ou, à tout le moins, qu'il était à même, compte tenu de ses fonctions et de ses liens familiaux, d'influencer le cours des événements en Syrie. Son inscription sur l'annexe de l'aO-Syrie puis de l'O-Syrie était ainsi justifiée. F. Agissant par la voie du recours en matière de droit public, Hafez Makhlouf demande au Tribunal fédéral, sous suite de frais et dépens, principalement, d'annuler l'arrêt du 14 juin 2012 ainsi que, dans la mesure où elles le concernent, l'aO-Syrie et l'O-Syrie et d'ordonner au Département fédéral de l'économie et à toute autorité compétente de lever toutes les mesures prises à son encontre; à titre subsidiaire, il conclut à ce que l'arrêt du 14 juin 2012 soit annulé et la cause renvoyée à l'autorité précédente pour nouvelle décision dans le sens des considérants. L'autorité précédente a renoncé à se déterminer sur le recours. Le Département a proposé de le rejeter. Le Conseil fédéral n'a pas déposé de détermination. Dans une écriture du 6 novembre 2012, le recourant s'est prononcé sur la prise de position du Département.