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 en raison de la situation en 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 des 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 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 16 août 2011 (RO 2011 3807), l'annexe 2 mentionnait en 33ème position "Mohammed Makhlouf (alias Abu Rami) ", avec les informations d'identification "né à Latakia (Syrie) le 19.10.1932" et les indications suivantes sous la rubrique "Fonction resp. motifs": "Proche associé et oncle maternel de Bachar et Mahir Al-Assad, associé d'affaires et père de Rami, Ihab et Iyad Makhlouf." Par acte du 16 septembre 2011, Mohamad Makhlouf a recouru au Tribunal administratif fédéral contre la modification du 16 août 2011 de l'annexe 2 de l'aO-Syrie. Il a conclu principalement à ce qu'il soit ordonné à l'autorité compétente de le radier de ladite annexe et à ce que les mesures de blocage frappant ses avoirs soient levées. C. 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 Mohamad Makhlouf. Par arrêt du 14 juin 2012, le Tribunal administratif fédéral est entré en matière sur le recours de Mohamad Makhlouf et l'a rejeté. Sur le plan de la recevabilité, il a considéré que Mohamad 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 Mohamad Makhlouf "est ou sera mis au service du maintien du régime". Son inscription sur l'annexe de l'aO-Syrie puis de l'O-Syrie était ainsi justifiée. D. Agissant par la voie du recours en matière de droit public, Mohamad 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 dans sa teneur du 16 août 2011 et l'O-Syrie et d'ordonner au Département 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.