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 C.X._ et D.X._, nés respectivement le *** 1986 et le *** 1987.
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 de C.X._ et D.X._, à savoir leurs parents et leurs grands-mères. Leurs parents - qui seuls sont encore parties à la procédure devant le Tribunal de céans - 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): 526'535 fr.; B.X._ (mère): 548'157 fr. 50. 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._ et D.X._, à titre de réparation du tort moral, une somme de 66'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._ et D.X._. Sur le fond, ils ont pris des conclusions tendant à ce que Skyguide soit condamnée à leur verser à chacun 39'668 fr. 75 à 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, 10'000 fr. supplémentaires à titre de réparation du tort moral, ainsi que 2'000 fr. "à titre de dépens, comprenant les frais d'expertise et une participation aux honoraires de [leur] 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'<ref-law>. 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 amplifié les conclusions contenues dans le mémoire du 29 janvier 2007 tendant à l'allocation d'indemnités à titre de réparation du tort moral supérieures à celles octroyées par Skyguide. Ils ont également modifié les conclusions initiales tendant à l'allocation d'indemnités pour la perte de soutien, en les augmentant pour les parents. Les parents de C.X._ et D.X._ demandaient dorénavant le versement à chacun d'eux de 60'000 fr. supplémentaires au moins pour le tort moral et de 200'000 fr., mais au moins 150'000 fr., pour la perte de soutien. Ils concluaient en outre à l'allocation à chacun de 4'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 si les recourants avaient valablement conclu, dans le délai de recours, à l'allocation à chacun d'eux, à titre de réparation du tort moral, d'une somme supplémentaire par rapport à l'indemnité qui leur avait été allouée par Skyguide, les conclusions amplifiées contenues dans le mémoire du 14 mars 2008 étaient irrecevables. En effet, les conclusions étant scellées par le mémoire de recours (cf. art. 52 al. 1 première phrase de la loi fédérale du 20 décembre 1968 sur la procédure administrative [PA; RS 172.021]) déposé dans le délai légal non prolongeable (<ref-law>) de 30 jours à compter de la notification de la décision attaquée (<ref-law>), celles prises ultérieurement dans le mémoire complémentaire du 14 mars 2008 étaient irrecevables. Sur le fond, les conclusions, jugées recevables, tendant à l'allocation à chacun des père et mère d'un montant supplémentaire de 10'000 fr. à titre de réparation du tort moral, ont été rejetées, tout comme les prétentions en indemnisation de la perte de soutien.
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 60'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.

Considérant en droit:
1. 1.1 Dirigé contre un jugement final (cf. <ref-law>) rendu dans une cause de droit public (cf. <ref-law>) par le Tribunal administratif fédéral (cf. <ref-law>), le présent recours est en principe recevable comme recours en matière de droit public. Interjeté par des parties directement touchées par la décision attaquée et qui ont un intérêt digne de protection à son annulation ou sa modification (cf. <ref-law>), il a, en effet, été déposé dans le délai (cf. <ref-law>) et la forme (cf. <ref-law>) prévus par la loi et ne tombe sous aucun des cas d'exceptions mentionnés à l'<ref-law>.
1.2 Selon l'<ref-law>, s'agissant de contestations pécuniaires, le recours est irrecevable en matière de responsabilité étatique si la valeur litigieuse est inférieure à 30'000 fr. Aux termes de l'<ref-law>, lorsque le recours est dirigé contre une décision finale, la valeur litigieuse est déterminée par les conclusions restées litigieuses devant l'autorité précédente. Selon une jurisprudence établie sous l'ancienne loi fédérale d'organisation judiciaire du 16 décembre 1943 (OJ; en vigueur jusqu'au 31 décembre 2006), qui demeure valable sous la LTF, les chefs de conclusions qui ne sont plus litigieux devant le Tribunal fédéral ne sont pris en considération pour le calcul de la valeur litigieuse que s'ils présentent un lien de connexité avec ceux qui le sont encore (<ref-ruling> consid. 1.2 p. 239). Par ailleurs, l'<ref-law> prévoit que les conclusions prises par des consorts sont additionnées, à moins qu'elles ne s'excluent.
En l'occurrence, devant l'autorité précédente, les recourants ont conclu (dans leur mémoire complémentaire du 14 mars 2008) à ce qu'un montant de 60'000 fr. (au lieu des 10'000 fr. demandés dans leur mémoire initial) leur soit alloué à chacun à titre de réparation du tort moral. Ces conclusions sont reprises dans le présent recours. Devant le Tribunal administratif fédéral, les recourants avaient en outre fait valoir des prétentions en indemnisation de la perte de soutien, auxquelles ils ont renoncé dans la présente procédure. Additionnées pour tenir compte de la consorité (2 x 60'000 = 120'000 fr.), les conclusions prises au titre de la réparation du tort moral atteignent à elles seules la limite de valeur litigieuse de 30'000 fr. Il convient par conséquent d'admettre que cette condition de recevabilité est également remplie, sans qu'il soit besoin de se prononcer sur la prise en considération des conclusions formulées devant l'autorité précédente au titre de l'indemnisation de la perte de soutien.
1.3 On peut se demander si les conclusions des recourants devant le Tribunal de céans, ainsi que la motivation présentée à l'appui de celles-ci, tiennent suffisamment compte du fait que l'autorité précédente n'est entrée en matière sur les prétentions en réparation du tort moral qu'à hauteur de la somme de 10'000 fr. chacun initialement requise. Jusqu'à concurrence de ce montant de 10'000 fr., leurs conclusions ne sauraient toutefois prêter le flanc à la critique d'un point de vue formel, de sorte que la question évoquée ci-dessus ne doit être tranchée que si le Tribunal de céans parvient à la conclusion que les recourants peuvent prétendre, sur le fond, à un montant supérieur.
2. Les conditions d'application de la loi fédérale du 14 mars 1958 sur la responsabilité de la Confédération, des membres de ses autorités et de ses fonctionnaires (loi sur la responsabilité; LRCF; RS 170.32) ont été présentées de manière exacte et complète par l'autorité précédente, de sorte qu'il suffit ici de renvoyer aux considérants pertinents de la décision entreprise. Il en va de même pour ce qui a trait à la nature juridique de l'intimée.
3. 3.1 Les recourants estiment que le montant adjugé par le Tribunal administratif fédéral est manifestement trop bas. Ils se fondent essentiellement sur les tabelles établies par la doctrine recensant les cas d'adjudication de sommes d'argent à titre de réparation du tort moral (voir not. Klaus Hütte/Petra Ducksch/Alexandre Gross/Kayum Guerrero, Le tort moral: tableaux de jurisprudence comprenant des décisions judiciaires rendues de 1990 à 2005, 3ème éd.). Ils se prévalent également de différentes autres affaires dont la presse s'est faite l'écho et de ce que l'intimée aurait versé des sommes bien plus importantes dans le cadre de la liquidation transactionnelle du litige avec d'autres parties.
3.2 La fixation de l'indemnité pour tort moral est une question d'application du droit fédéral, que le Tribunal fédéral examine donc librement (cf. <ref-law>). Dans la mesure où celle-ci relève pour une part importante de l'appréciation des circonstances, le Tribunal fédéral intervient avec retenue. Il le fait notamment si l'autorité précédente a mésusé de son pouvoir d'appréciation, en se fondant sur des considérations étrangères à la disposition applicable, en omettant de tenir compte d'éléments pertinents ou encore en fixant une indemnité inéquitable parce que manifestement trop faible ou trop élevée (arrêt 4C.84/2005 du 16 juin 2005 consid. 6). Comme il s'agit toutefois d'une question d'équité - et non pas d'une question d'appréciation au sens strict, qui limiterait son examen à l'abus ou à l'excès du pouvoir d'appréciation -, le Tribunal fédéral examine librement si la somme allouée tient suffisamment compte de la gravité de l'atteinte ou si elle est disproportionnée par rapport à l'intensité des souffrances morales causées à la victime (<ref-ruling> consid. 5.1 p. 705; arrêt 4C.84/2005, précité, consid. 6).
3.2 La fixation de l'indemnité pour tort moral est une question d'application du droit fédéral, que le Tribunal fédéral examine donc librement (cf. <ref-law>). Dans la mesure où celle-ci relève pour une part importante de l'appréciation des circonstances, le Tribunal fédéral intervient avec retenue. Il le fait notamment si l'autorité précédente a mésusé de son pouvoir d'appréciation, en se fondant sur des considérations étrangères à la disposition applicable, en omettant de tenir compte d'éléments pertinents ou encore en fixant une indemnité inéquitable parce que manifestement trop faible ou trop élevée (arrêt 4C.84/2005 du 16 juin 2005 consid. 6). Comme il s'agit toutefois d'une question d'équité - et non pas d'une question d'appréciation au sens strict, qui limiterait son examen à l'abus ou à l'excès du pouvoir d'appréciation -, le Tribunal fédéral examine librement si la somme allouée tient suffisamment compte de la gravité de l'atteinte ou si elle est disproportionnée par rapport à l'intensité des souffrances morales causées à la victime (<ref-ruling> consid. 5.1 p. 705; arrêt 4C.84/2005, précité, consid. 6).
3.3 3.3.1 Le Tribunal administratif fédéral a procédé conformément aux réquisits de la jurisprudence pour fixer l'indemnité due à titre de réparation du tort moral, selon une méthode s'articulant en deux phases (cf. <ref-ruling> consid. 2.2.3 p. 120 et les références). La première consiste à déterminer une indemnité de base, de nature abstraite, alors que la seconde implique une adaptation de cette somme aux circonstances du cas d'espèce. Dans ce processus, il convient de ne pas perdre de vue qu'une indemnité pécuniaire sera toujours impropre à compenser la perte d'un proche; elle doit néanmoins être fixée en tentant de prendre en compte l'intensité des relations personnelles entre le défunt et les requérants au moment du décès (arrêt 1C_284/2008 du 1er avril 2009 consid. 5.2). Il faut également rappeler que la détermination concrète de ce qui est dû de ce chef et qui dépend de l'ensemble des circonstances du cas d'espèce rend illusoire toute comparaison linéaire avec d'autres précédents pour tenter d'en déduire un droit ferme à l'adjudication d'une somme supérieure. Ces principes ont été exposés de manière exacte au consid. 10.1.2 de l'arrêt entrepris et il peut y être renvoyé.
3.3.2 En premier lieu, le Tribunal administratif fédéral a à juste titre pu relever que les précédents dans lesquels les autorités judiciaires ont dû allouer des indemnités pour tort moral suite à la perte de deux enfants sont fort rares, ce qui rend délicate la phase de comparaison abstraite. Ceci l'a conduit à faire état de précédents dans lesquels les parents ont été indemnisés pour la douleur subie par la perte d'un enfant, en précisant toutefois immédiatement qu'il était délicat de se contenter de multiplier de telles sommes par deux. Les arrêts auxquels l'autorité précédente se réfère à titre d'éléments pour la comparaison de base retiennent ainsi des sommes comprises entre 20'000 fr. et 35'000 fr. en cas de perte d'un enfant (cf. ég. Hütte/Ducksch/Gross/Guerrero, op. cit.). La moyenne varie au gré du temps et des cas particuliers mis en évidence par la jurisprudence. Ainsi, les auteurs précités font état, pour la période allant de 1998 à 2000, de montants allant de 20'000 fr. à 25'000 fr. (Vol. 2, III/1 à III/8), pour celle de 2001 à 2002, de sommes de 30'000 fr. à 35'000 fr. (Vol. 2, III/1 à III/7) et pour celle de 2003 à 2005, de montants de 22'000 fr. à 30'000 fr. (Vol. 2, III/1 à III/7). L'affaire à la base de l'<ref-ruling>, à laquelle le Tribunal administratif fédéral se réfère au considérant 10.2.1.1 in fine de son arrêt, est la plus proche, au plan de l'état de fait, de celle qui fait l'objet du présent recours. Or, à cette occasion, le Tribunal fédéral avait alloué à un père un montant de 40'000 fr. à titre de réparation du tort moral consécutif au décès de deux de ses enfants, tués par la chute d'un avion. Le choc nerveux subi à cette occasion l'avait au surplus gravement atteint dans sa santé. Ces circonstances se rapprochent ainsi de celles du cas d'espèce, sauf pour ce qui est des conséquences de ce tragique accident sur la santé des parents, dont il n'est pas fait mention en la présente cause.
3.3.3 En second lieu, les critères mis en évidence par le Tribunal administratif fédéral pour adapter ces montants abstraits aux particularités de l'espèce sont également pertinents. Il en va ainsi de la faute de l'auteur, du fait que le décès soit survenu loin de la patrie du défunt, de la mort soudaine et inattendue, des problèmes liés au travail de deuil lors de la perte d'un proche, du décès d'un enfant en pleine jeunesse, de la perte des espoirs que les parents avaient placés en lui, du comportement du responsable pendant le procès civil ou pénal etc., aspects qui ont tous été évoqués par le Tribunal administratif fédéral et il peut là aussi être renvoyé aux considérants pertinents de l'arrêt entrepris. Contrairement à ce qu'affirment les recourants, l'autorité précédente a intégré la faute de Skyguide à son raisonnement. On peut se contenter de relever ici que, dans la mesure où le bénéficiaire domicilié à l'étranger serait exagérément avantagé en raison des conditions économiques et sociales existant à son lieu de domicile, il convient d'adapter l'indemnité vers le bas, en précisant toutefois qu'il ne saurait y avoir une correspondance mathématique entre le niveau des salaires au domicile à l'étranger par rapport à celui existant en Suisse et l'impact que cette divergence pourrait avoir sur le montant de l'indemnité pour tort moral (<ref-ruling> consid. 4b p. 560; <ref-ruling> consid. 4 p. 11 ss). Le Tribunal administratif fédéral, comme Skyguide, ne s'est pas étendu plus avant sur cet élément qui a néanmoins été évoqué.
3.3.4 Les autres arguments des recourants relatifs à la fixation du montant de la réparation du tort moral sont soit dénués de pertinence (ainsi p. ex. les condamnations soi-disant prononcées par le Tribunal de Saint-Nazaire dans l'affaire du Queen Elisabeth II au titre du préjudice d'angoisse ou la non-application de la loi fédérale du 23 mars 2007 sur l'aide aux victimes d'infractions [LAVI; RS 312.5] au cas d'espèce), soit difficilement compréhensibles. Le fait que l'intimée, dans le cadre de la liquidation transactionnelle du litige avec certains proches de victimes leur aurait adjugé des montants supérieurs à ceux obtenus par la voie judiciaire n'est pas davantage pertinent. C'est en effet le propre de la transaction que de reposer sur une estimation des risques d'un procès, ainsi que du temps, du coût et de l'énergie qu'implique son suivi. Tous ces éléments interfèrent sur la proposition transactionnelle, comme d'autres considérations de nature plus immatérielle, telles que, par exemple, la volonté d'afficher publiquement le fait d'assumer volontairement les conséquences de ses actes.
3.3.5 Au vu de ce qui précède, le montant de 66'000 fr. alloué à chacun des parents des deux enfants disparus dans l'accident correspond tant aux standards prévalant de manière abstraite en ce domaine qu'aux circonstances particulières du cas d'espèce.
3.3.6 Les recourants n'ayant pas droit, sur le fond, à un montant supérieur à la somme de 66'000 fr. chacun que l'intimée a accepté de leur verser au titre de la réparation du tort moral par décisions du 11 décembre 2006, la question de la recevabilité des conclusions soulevée au consid. 1.3 ci-dessus peut demeurer indécise.
4. Les considérants qui précèdent conduisent au rejet du recours, dans la mesure où il est recevable. Le recours étant d'emblée dénué de chances de succès, la requête d'assistance judiciaire est rejetée (cf. <ref-law>).
Succombant, les recourants doivent supporter les frais judiciaires, solidairement entre eux (cf. art. 65 et 66 al. 1 et 5 LTF). Ils n'ont pas droit à des dépens (cf. <ref-law>).
Conformément à la règle de l'<ref-law> (cf. aussi <ref-ruling> consid. 7 p. 119; arrêt 2C_212/2007 du 11 décembre 2007 consid. 5), l'intimée n'a pas droit à des dépens.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La requête d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge des recourants, solidairement entre eux.
4. Le présent arrêt est communiqué aux mandataires des parties et au Tribunal administratif fédéral, Cour I.
Lausanne, le 28 avril 2011
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Vianin