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 trouvait C.X._, née le *** 1990. 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 les parents de C.X._. Ces derniers ont conclu au versement des sommes d'argent suivantes, à 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: A.X._ (père): 263'267 fr. 50; B.X._ (mère): 274'078 fr. 75. Ils ont 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 leur 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écisions du 11 décembre 2006, Skyguide a octroyé à chacun des parents de C.X._, à titre de réparation du tort moral, une somme de 33'000 fr. avec intérêts à 5 % l'an depuis le 1er juillet 2002. En sus, Skyguide a accordé à chaque requérant 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é les requêtes 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 figuraient les parents de C.X._. Sur le fond, ils ont pris des conclusions tendant à ce que Skyguide soit condamnée à leur verser à chacun 21'113 fr. 15 à titre d'indemnisation de la perte de soutien, en sus des montants accordés par décisions du 11 décembre 2006. Ils ont en outre conclu à ce que leur soient alloués, à chacun, 2'000 fr. "à titre de dépens, comprenant les frais d'expertise et une participation aux honoraires de [leur] conseil suisse". Ils n'ont en revanche pas adopté de conclusions tendant à l'octroi d'un montant supplémentaire à titre de réparation du tort moral. 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, ce qu'ils n'avaient pas fait dans leur mémoire du 29 janvier 2007. Ils ont en outre amplifié les conclusions initiales tendant à l'allocation d'indemnités pour la perte de soutien. Les parents de C.X._ demandaient dorénavant le versement à chacun d'eux de 28'000 fr. supplémentaires au moins pour le tort moral et de 110'000 fr., mais au moins 90'000 fr., pour la perte de soutien. Ils concluaient en outre à l'allocation à chacun de 2'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 rejeté le recours dans la mesure de sa recevabilité. 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 en réparation du tort moral 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. Quant aux prétentions en indemnisation de la perte de soutien, elles ont été rejetées. C. Agissant par la voie du recours en matière de droit public, A.X._ et B.X._ demandent au Tribunal fédéral, principalement, de condamner Skyguide à leur verser à chacun 28'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. Ils requièrent aussi la dispense de l'avance des frais de procédure et la désignation de leur 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.