Faits: A. Par arrêté du 6 avril 2009, le Conseil municipal de la Ville de Genève (ci-après: le Conseil municipal) a délivré un préavis favorable au projet de loi modifiant les limites de la zone inconstructible et du périmètre de protection des rives du lac n° 29691-228, concernant le centre William-Rappard, afin de permettre l'extension de ce bâtiment occupé par l'Organisation mondiale du commerce. Le référendum lancé contre cette délibération ayant abouti, le Conseil d'Etat du canton de Genève a fixé au 27 septembre 2009 la date de la votation. Le 7 septembre 2009, B._, C._ et A._, citoyens de la commune de Genève, ont déposé auprès du Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif) deux actes de recours, l'un annulant et remplaçant le second. Ils ont fait valoir que la brochure éditée par la Ville de Genève, destinée à l'ensemble des citoyens à l'occasion de la votation sur l'objet précité comportait des explications fallacieuses de nature à tromper les citoyens. Ils se sont plaints d'une violation de la liberté de vote (art. 34 al. 2 Cst.) et ont conclu à ce que la votation soit annulée "dans l'hypothèse où le référendum serait rejeté". Ils ont déposé différents compléments à leur recours, les 9, 11 et 25 septembre 2009. Par décision du 23 septembre 2009, le Tribunal administratif a appelé en cause le Comité "X._", auteur d'un tract "tous ménages" également litigieux. Le 27 septembre 2009, l'arrêté du Conseil municipal du 6 avril 2009 a été accepté par 61,8% des votants. Par arrêt du 8 décembre 2009, le Tribunal administratif a déclaré le recours irrecevable, au motif que les conclusions des recourants étaient conditionnelles. B. Agissant par la voie du "recours en matière publique", A._ et B._ demandent au Tribunal fédéral d'annuler cet arrêt. Ils estiment que le Tribunal administratif a arbitrairement considéré que les conclusions du recours étaient conditionnelles et qu'il a ainsi commis un déni de justice. Le Tribunal administratif s'en rapporte à justice quant à la recevabilité du recours et persiste dans les considérants et le dispositif de son arrêt. La Ville de Genève, la Chancellerie d'Etat du canton de Genève et le Comité "X._" concluent au rejet du recours, dans la mesure de sa recevabilité. 