Faits: Faits: A. X._, né en 1971, possède conjointement les nationalités suisse et française. Il a vécu en France où il a été exempté du service national actif par la Commission locale d'aptitude siégeant à Marseille le 20 mars 1990 avant de s'établir en Suisse le 1er juin de la même année. D'abord installé à A._ (VS), il a déménagé à B._ (VS) en 1996, commune au sein de laquelle il a changé de domicile à plusieurs reprises. Un livret de service a été établi au nom de X._ par le chef de section militaire (ci-après: le chef de section) de B._ à l'occasion d'un changement d'adresse. Suite à cette mesure, le 7 octobre 2003, l'Office cantonal des affaires militaires (ci-après: l'Office cantonal) a réclamé le paiement de taxes d'exemption de l'obligation de servir (ci-après: la taxe d'exemption) pour les périodes d'assujettissement 1997 à 2002 (soit les périodes de taxation 1998 à 2003) à l'intéressé qui a contesté cette décision. Le 19 décembre 2003, l'Etat-major général de l'armée suisse (ci-après: l'Etat-major) a décidé que X._ ne pourrait pas être incorporé dans l'armée suisse, qu'il était affecté aux doubles nationaux non incorporés et qu'il n'était pas astreint au service militaire. L'Office cantonal a considéré que la décision de l'Etat-major ne déployait d'effets que pour l'avenir. En conséquence, il a refusé à X._ l'exonération des taxes d'exemption litigieuses, d'abord par décision du 3 mars 2004, puis par décision sur réclamation du 16 juin 2004. Par arrêt du 22 décembre 2004, la Commission cantonale de recours en matière fiscale du canton du Valais (ci-après: la Commission cantonale de recours) a rejeté le recours formé par X._. Elle a considéré, en bref, que la décision de l'Etat-major affectant X._ aux doubles nationaux non incorporés n'avait pas d'effet rétroactif et qu'en conséquence, l'intéressé était astreint au paiement des taxes d'exemption litigieuses. Par arrêt du 22 décembre 2004, la Commission cantonale de recours en matière fiscale du canton du Valais (ci-après: la Commission cantonale de recours) a rejeté le recours formé par X._. Elle a considéré, en bref, que la décision de l'Etat-major affectant X._ aux doubles nationaux non incorporés n'avait pas d'effet rétroactif et qu'en conséquence, l'intéressé était astreint au paiement des taxes d'exemption litigieuses. B. Agissant par la voie du recours de droit administratif, X._ demande principalement au Tribunal fédéral d'annuler l'arrêt de la Commission cantonale de recours du 22 décembre 2004 et de lui allouer une indemnité d'un montant de 1'000 fr., à titre de réparation du tort moral. Il demande subsidiairement l'annulation partielle de l'arrêt de la Commission cantonale de recours du 22 décembre 2004 en raison de la prescription partielle de la dette ainsi qu'une indemnité d'un montant de 500 fr., à titre de réparation du tort moral. En outre, X._ sollicite l'assistance judiciaire. La Commission cantonale de recours, l'Office cantonal ainsi que l'Administration fédérale des contributions concluent au rejet du recours. La Commission cantonale de recours, l'Office cantonal ainsi que l'Administration fédérale des contributions concluent au rejet du recours. C. Par ordonnance présidentielle du 21 avril 2005, l'effet suspensif a été conféré au recours.