Faits: A. Dans la nuit du 1er au 2 juillet 2002, deux avions commerciaux, à savoir un Tupolev TU154M de Bashkirian Airlines qui reliait Moscou à Barcelone (vol BTC2937) et un Boeing B757-200PF de la compagnie DHL (vol DHX611), lequel reliait Bahrein à Bruxelles via Bergame, sont entrés en collision au-dessus d'Überlingen (Allemagne), près du Lac de Constance. Les septante et une personnes, passagers et membres d'équipage, qui se trouvaient à bord des appareils ont perdu la vie. Le contrôle du trafic aérien sur la portion du territoire du sud de l'Allemagne où les deux avions se trouvaient lors de la collision incombait à la société Skyguide, Société Anonyme Suisse pour les Services de la Navigation Aérienne civils et militaires (ci-après: Skyguide). Parmi les passagers du vol de Bashkirian Airlines, décédés lors de cette collision, se trouvaient B.X._, C.X._ et D.X._, nés respectivement le *** 1964, le *** 1987 et le *** 1989. Par requête unique et conjointe du 19 mai 2005, cent vingt-trois proches de passagers du Tupolev, victimes du crash aérien, se sont adressés à Skyguide afin d'être dédommagés. Parmi ceux-ci figuraient plusieurs membres de la famille des victimes précitées, à savoir leur époux et père, leurs parents et grands-parents, la grand-mère de C.X._ et de D.X._, le demi-frère des prénommés, issu d'un précédent mariage de A.X._, ainsi que les frère et soeur de B.X._. Leur époux et père, A.X._, qui seul est encore partie à la procédure devant le Tribunal de céans, a conclu au versement de 820'785 fr. 60 à titre de réparation du dommage - consistant en la perte de soutien et les frais, dont ceux d'inhumation, de voyage et d'autres coûts - et du tort moral subi, avec intérêts à 5% à compter du 1er juillet 2002. Il a en outre conclu à ce que les décisions de Skyguide soient rendues sans frais et à l'octroi d'une "équitable indemnité" valant participation aux honoraires de son conseil. Par décision incidente du 26 juillet 2005, Skyguide a disjoint les procédures relatives aux cent vingt-trois demandes. Le 31 mars 2006, les requérants ont sollicité le versement à chacun d'un montant complémentaire de 1'000 fr., à titre d'indemnité pour les frais résultant de la procédure (frais de traduction, de légalisation et d'apostille, de port, etc.). Par décision du 11 décembre 2006, Skyguide a octroyé à A.X._, à titre de réparation du tort moral, une somme de 120'000 fr. avec intérêts à 5 % l'an depuis le 1er juillet 2002. En sus, Skyguide lui a accordé un montant de 1'000 fr. à titre de dommages-intérêts, avec intérêts à 5 % l'an depuis le 31 mars 2006. Skyguide a rejeté sa requête pour le surplus, en particulier s'agissant de la perte de soutien. B. Le 29 janvier 2007, un certain nombre de proches des victimes de l'accident aérien ont recouru au Tribunal administratif fédéral. Parmi ceux-ci figurait A.X._. Sur le fond, il a pris des conclusions tendant à ce que Skyguide soit condamnée à lui verser 101'985 fr. à titre d'indemnisation de la perte de soutien, en sus du montant accordé par décision du 11 décembre 2006. Il a en outre conclu à ce qu'il lui soit alloué 6'000 fr. "à titre de dépens, comprenant les frais d'expertise et une participation aux honoraires de [son] conseil suisse". Le 18 mars 2007, les proches des victimes ont requis la suspension de la procédure jusqu'à droit connu dans la procédure pénale ouverte contre des employés de Skyguide devant le Tribunal de district de Bülach. Par décision incidente du 3 mai 2007, le Tribunal administratif fédéral a suspendu les procédures dans l'attente de la notification des jugements du Tribunal précité. Le 5 septembre 2007, le Tribunal de district de Bülach a transmis au Tribunal administratif fédéral les jugements en matière pénale rendus le 21 août 2007 à l'encontre de huit employés de Skyguide. Quatre d'entre eux ont été reconnus coupables d'homicide par négligence au sens de l'art. 117 CP. Ils ont été condamnés respectivement, pour trois d'entre eux, à une peine de 12 mois d'emprisonnement avec sursis durant deux ans et, pour le quatrième, à une peine de 90 jours amende à 150 fr. Les autres employés ont été acquittés. Le 23 octobre 2007, le Tribunal administratif fédéral a ordonné la reprise de la procédure. Il a en outre autorisé la consultation par les parties de l'essentiel des documents pénaux, leur a imparti un délai pour motiver leur requête d'assistance judiciaire en décrivant la situation financière dans laquelle elles se trouvaient dans leur pays et leur a permis de déposer un mémoire complémentaire. Le délai imparti aux proches des victimes pour établir leur situation financière et produire un mémoire complémentaire a été prolongé, à leur demande, à de multiples reprises. Le 14 mars 2008, au terme de l'ultime prolongation, les proches des victimes ont déposé un mémoire complémentaire contenant certains éléments relatifs à leur situation personnelle et patrimoniale et étayé leur demande d'assistance judiciaire à l'aide de pièces. Par ailleurs, ils ont pris des conclusions additionnelles tendant à l'allocation d'indemnités à titre de réparation du tort moral supérieures à celles octroyées par Skyguide. Ils ont en outre amplifié les conclusions initiales tendant à l'allocation d'indemnités pour la perte de soutien. A.X._ demandait dorénavant 120'000 fr. supplémentaires pour le tort moral et 360'000 fr., mais au moins 180'000 fr., pour la perte de soutien. Il concluait en outre à l'allocation de 6'000 fr. à titre de dépens, montant comprenant les frais d'expertise et une participation aux honoraires du conseil suisse. Dans sa réponse du 29 octobre 2008, Skyguide a conclu préalablement à ce que le mémoire complémentaire du 14 mars 2008 soit déclaré irrecevable dans la mesure où il contenait des conclusions nouvelles ou amplifiées. Par arrêt du 17 février 2010, le Tribunal administratif fédéral a partiellement admis le recours de A.X._, dans la mesure de sa recevabilité. Il lui a adjugé, au titre de l'indemnisation de la perte de soutien, un montant supplémentaire de 6'032 fr. 80 avec intérêts à 5% l'an depuis le 1er juillet 2002. En substance, pour ce qui intéresse encore la cause telle qu'elle se présente devant le Tribunal de céans, le Tribunal administratif fédéral a retenu que les conclusions nouvelles prises au titre de la réparation du tort moral, comme celles amplifiées concernant la perte de soutien, avaient été adoptées tardivement, n'ayant été formulées que dans le mémoire complémentaire du 14 mars 2008. Elles étaient par conséquent irrecevables. C. Agissant par la voie du recours en matière de droit public, A.X._ demande au Tribunal fédéral, principalement, de condamner Skyguide à lui verser 120'000 fr. supplémentaires à titre de réparation du tort moral et, subsidiairement, de renvoyer la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants, le tout sous suite de frais et dépens. Il requiert aussi la dispense de l'avance des frais de procédure et la désignation de son mandataire en qualité d'avocat d'office. L'autorité précédente a renoncé à se déterminer sur le recours, alors que l'intimée a conclu à son irrecevabilité, subsidiairement à son rejet, le tout sous suite de frais et dépens.