Faits:
A. X._ n'a pas été incorporé dans une formation de l'armée, ni astreint au service civil. Il n'a effectué aucun jour de service civil durant l'année 2003.
Le 27 février 2008, le Service de la taxe d'exemption de l'obligation de servir appartenant à l'Administration fiscale cantonale du canton de Genève (ci-après: l'Administration fiscale cantonale) a transmis à X._ un bordereau de taxe d'exemption de l'obligation de servir 2003. Selon ce document, la taxe pour l'année 2003 était fixée à 1'000 fr., sur lesquels 850 fr. étaient encore dus.
Le 7 mai 2008, l'Administration fiscale cantonale a rejeté la réclamation élevée par X._.
Par arrêt du 9 décembre 2008, le Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif) a rejeté le recours formé par X._ à l'encontre de la décision du 7 mai 2008.
B. Contre l'arrêt du 9 décembre 2008, X._ a interjeté un "recours de droit public" au Tribunal fédéral. Il conclut à l'annulation de l'arrêt entrepris et à ce que la jurisprudence dégage une interprétation de l'art. 59 al. 3 Cst. conforme à la CEDH.
Le Tribunal administratif n'a pas présenté d'observations, s'en rapportant à justice quant à la recevabilité du recours et renvoyant à son arrêt sur le fond. L'Administration fiscale cantonale s'en remet à justice quant à la recevabilité du recours et conclut à son rejet dans la mesure de sa recevabilité, avec suite de frais.
L'Administration fédérale des contributions déclare se rallier à l'arrêt attaqué.

Considérant en droit:
1. 1.1 Le présent recours est dirigé contre une décision rendue dans une cause de droit public (art. 82 let. a de la loi du 17 juin 2005 sur le Tribunal fédéral [LTF; RS 173.110]) par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2 LTF), sans qu'aucune des exceptions prévues à l'<ref-law> ne soit réalisée, de sorte que la voie du recours en matière de droit public est en principe ouverte.
1.2 L'intitulé erroné du mémoire de recours, qualifié de "recours de droit public" ne saurait porter préjudice au recourant, pour autant que son écriture remplisse les conditions formelles de la voie de droit appropriée (<ref-ruling> consid. 1.2 p. 302 s., 308 consid. 4.1 p. 314).
Lorsque, comme en l'espèce, le recourant agit personnellement et non par l'entremise d'un professionnel qualifié, l'interdiction du formalisme excessif impose de ne pas se montrer trop strict dans l'énoncé des conclusions si, à la lecture du mémoire de recours, on comprend aisément ce que veut l'intéressé (arrêt 2C_564/2008 du 12 septembre 2008 consid. 1.1). La conclusion demandant au Tribunal fédéral de dégager une interprétation conforme à la CEDH est irrecevable, car elle ne se rapporte pas à l'arrêt attaqué. Hormis cette conclusion, le recourant demande l'annulation de l'arrêt attaqué. Dans la mesure où l'on parvient à comprendre qu'il conteste la taxe mise à sa charge, sa conclusion purement cassatoire peut être admise (cf. <ref-ruling> consid. 1.4.1 p. 414 s.).
Pour le surplus, le recours a été déposé en temps utile compte tenu des féries (art. 100 al. 1 et 46 al. 1 let. c LTF), par le destinataire de l'acte attaqué qui a un intérêt digne de protection à son annulation ou à sa modification, de sorte qu'il faut lui reconnaître la qualité pour recourir (<ref-law>). Il convient donc de se pencher sur les griefs soulevés.
2. 2.1 Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a ainsi que 106 al. 1 LTF), ce qui ne dispense cependant pas le recourant d'exposer succinctement en quoi l'acte attaqué viole le droit (<ref-law>). Le Tribunal fédéral n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant conformé- ment au principe d'allégation (<ref-law>). Il appartient ainsi au recourant de démontrer par une argumentation précise, en quoi consiste la violation des droits fondamentaux dont il se prévaut (<ref-ruling> consid. 3.2 p. 88 et les arrêts cités). En outre, le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il peut cependant rectifier ou compléter d'office les constatations de l'autorité précédente si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>; cf. aussi <ref-law>).
2.2 Le recourant soutient d'une part que les faits ont été établis en violation du droit au sens de l'<ref-law>. Il n'explique toutefois nullement à quelle(s) constatation(s) de fait il se réfère concrètement et rien, dans son argumentation, ne permet de le déduire. Dépourvu de motivation (cf. <ref-law>), le grief est donc irrecevable.
2.3 Le recourant reproche d'autre part au Tribunal administratif de l'avoir discriminé d'une façon contraire à l'art. 8 Cst. et à l'art. 14 CEDH. Comme le relève pertinemment l'Administration fiscale cantonale, le recourant n'expose cependant pas quelle serait concrètement la discrimination dont il se prévaut: il se réfère à une définition figurant dans le Dictionnaire Le Robert, édition 1993, et formule, dans la partie en fait de son mémoire, des considérations générales sur le système de taxe prévu à l'art. 59 al. 3 Cst. et concrétisé dans la loi fédérale du 12 juin 1959 sur la taxe d'exemption de l'obligation de servir (LTEO; RS 661), en résumant le contenu de l'arrêt attaqué; dans la partie en droit, il n'explique pas en quoi il aurait lui-même été discriminé par l'arrêt attaqué, ni dans quelle mesure la solution retenue sur le plan cantonal serait contraire à l'art. 8 Cst. ou à l'art. 14 CEDH.
Une telle motivation ne remplit pas les conditions de l'<ref-law> et n'est donc pas admissible.
3. Dans ces circonstances, le recours doit être déclaré irrecevable. Les frais seront mis à la charge du recourant qui succombe (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au recourant, au Service de la taxe d'exemption de l'obligation de servir, Administration fiscale cantonale, et au Tribunal administratif du canton de Genève ainsi qu'à l'Administration fédérale des contributions, Section de la taxe d'exemption de l'obligation de servir.
Lausanne, le 22 décembre 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Müller Dupraz