Faits: A. A._, ressortissant d'Afghanistan, est arrivé en Suisse le 11 novembre 2010. Il a formé le même jour une demande d'asile auprès du Centre d'enregistrement et de procédure de Chiasso. Dans le procès-verbal de son interpellation par la police le 11 novembre 2010, l'intéressé est indiqué comme étant né le 1er janvier 1994. Lors de sa première audition le 23 novembre 2010 par le Centre d'enregistrement et de procédure de Chiasso, il a déclaré être né le 3ème mois de 1373 selon le calendrier islamique (ce qui correspond au mois de mai/juin 1994). Le procès-verbal a ainsi mentionné la date du 1er mai 1994. L'Office fédéral des migrations (ci-après: l'ODM) a procédé à une évaluation des données relatives à la question de l'âge fournies dans le cadre de la collecte des données personnelles. Il a considéré l'intéressé comme majeur. En effet, celui-ci n'avait présenté aucun document d'identité, n'avait pas fait valoir de motifs valides pour expliquer l'absence de tels documents, avait fait des déclarations trop imprécises sur sa famille et s'était trompé sur les données de son parcours scolaire et professionnel. L'ODM a aussi retenu que A._ ressemblait physiquement à une personne majeure et que l'examen médical osseux de sa main avait déterminé que son âge était celui d'une personne de plus de dix-huit ans. La date de naissance du 1er janvier 1992 a été introduite dans le système d'information central sur la migration SYMIC (ci-après: le système SYMIC). B. Le 6 janvier 2011, A._ a déposé une demande de rectification des données personnelles auprès de l'ODM. Il souhaitait que sa date de naissance, selon lui le 25 mai 1994, soit modifiée dans le système SYMIC. A l'appui de sa requête, il a produit un document en original, édicté par un office de l'administration locale d'Hérat (Afghanistan) et certifié par le Ministère des affaires intérieures, indiquant pour date de naissance le quatrième jour du troisième mois de 1373 selon le calendrier islamique, correspondant au 25 mai 1994 du calendrier julien. Ce document lui aurait été remis par son grand-père vivant en Afghanistan, qui l'aurait lui-même obtenu des autorités deux ans plus tôt. Par décision du 8 juillet 2011, l'ODM a rejeté cette requête, faisant valoir que le document produit n'était pas de nature à remettre en cause son point de vue ainsi que la date de naissance du 1er janvier 1992. Par arrêt du 8 décembre 2011, le Tribunal administratif fédéral (ci-après: le TAF) a rejeté le recours de A._ contre la décision précitée. Il a considéré en substance que le document fourni n'avait pas de force probante suffisante. Par ailleurs, l'intéressé avait fait des déclarations contradictoires au cours de ses auditions et l'examen médical osseux du 15 novembre 2010 confirmait que son âge se différenciait significativement de celui déclaré. C. Agissant par la voie du "recours de droit public", A._ demande au Tribunal fédéral d'annuler l'arrêt du TAF du 8 décembre 2011 et d'inviter l'ODM à rectifier sa date de naissance dans le système SYMIC en inscrivant la mention du 25 mai 1994 en lieu et place de celle du 1er janvier 1992. Subsidiairement, il conclut à l'annulation de l'arrêt attaqué et au renvoi du dossier au TAF, respectivement à l'ODM, en vue d'une instruction complémentaire au sens des considérants. Plus subsidiairement, il requiert l'annulation partielle de l'arrêt attaqué, en ce sens que l'ODM est invité à mentionner dans le système SYMIC que la date de naissance du 1er janvier 1992 est litigieuse. Il requiert en outre l'assistance judiciaire. Le recourant se plaint d'une violation de la loi fédérale du 19 juin 1992 sur la protection des données (LPD; RS 235.1). Le TAF renonce à prendre position sur le recours. L'ODM, concluant implicitement au rejet du recours, soutient qu'il existe suffisamment d'éléments pour remettre en question l'affirmation du requérant selon laquelle il était mineur lors du dépôt de sa demande d'asile.