Faits : A. Par acte du 17 mars 2016 qualifié de décision, l'Aéroport International de Genève (ci-après : l'Aéroport) a retiré la carte d'identité aéroportuaire (également appelée CIA) de A._, employé d'une société de service indépendante de l'Aéroport. Cette carte permettait à l'intéressé d'accéder aux zones sécurisées situées sur le site. L'Aéroport a motivé ce retrait en expliquant que, dans le cadre d'un contrôle, les services de police genevois avaient indiqué posséder des renseignements défavorables au sujet de A._. Ceux-ci entraient en conflit avec les critères du Programme national de sûreté de l'aviation civile (aussi appelé NASP) qui prévalaient pour l'octroi de la carte d'identité aéroportuaire. Une voie de recours auprès du Tribunal administratif fédéral était mentionnée au terme de cet acte. B. Statuant sur recours de A._, le Tribunal administratif fédéral, par arrêt du 21 juillet 2016, a déclaré celui-ci irrecevable. Il a considéré en substance que l'Aéroport n'était pas habilité à rendre des décisions et que partant, comme il n'existait pas de décision attaquable, le Tribunal administratif fédéral était incompétent pour traiter du recours. C. A l'encontre de l'arrêt du 21 juillet 2016, A._ forme un recours en matière de droit public au Tribunal fédéral. Il conclut à l'annulation de l'arrêt attaqué et à celle de la décision adoptée le 17 mars 2016 par l'Aéroport. Il demande également que Me Pierre Bayenet soit désigné rétroactivement en qualité de conseil pour la procédure devant le Tribunal administratif fédéral et à ce que celui-ci soit indemnisé pour l'activité déployée, avec suite de frais et dépens devant les deux instances. Dans sa réponse, l'Aéroport s'en rapporte à justice quant à la recevabilité du recours au Tribunal fédéral et à l'instance compétente pour connaître du recours contre sa décision du 17 mars 2016, tout en demandant à ce que A._ soit débouté de toutes autres ou contraires conclusions. A titre subsidiaire, il demande le renvoi de la cause à l'instance compétente pour une instruction au fond. Le Département fédéral de l'environnement, des transports, de l'énergie et de la communication (ci-après : le Département fédéral) a renvoyé aux observations de l'Office fédéral de l'aviation civile (ci-après : l'Office fédéral). Ce dernier a déclaré renoncer à présenter des conclusions, tout en soulignant qu'à son avis, l'arrêt du Tribunal administratif fédéral ne souffrait d'aucune discussion. L'Aéroport a formé des observations au sujet de la prise de position de l'Office fédéral pour confirmer les fondements de sa compétence décisionnelle.