Faits: A. Par arrêté du 29 octobre 2008, publié dans la Feuille d'avis officiel du 31 octobre 2008, le Conseil d'Etat de la République et canton de Genève (ci-après: le Conseil d'Etat) a constaté l'aboutissement de l'initiative populaire cantonale intitulée "Pour le droit à un salaire minimum" (ci-après: l'initiative ou l'IN 142). Cette initiative porte sur l'adjonction, dans la Constitution genevoise, d'un art. 10B dont la teneur est la suivante: "L'Etat institue un salaire minimum cantonal, dans tous les domaines d'activité économique, en tenant compte des secteurs économiques ainsi que des salaires fixés dans les conventions collectives, afin que toute personne exerçant une activité salariée puisse disposer d'un salaire lui garantissant des conditions de vie décentes". Selon l'exposé des motifs, les initiants comptent apporter une solution aux conditions de travail et de salaires des travailleurs qui touchent une rémunération officiellement reconnue comme un "bas salaire". L'introduction d'un droit à un salaire minimum permettrait d'enrayer cette précarisation. Dans son rapport du 30 janvier 2009 au Grand Conseil de la République et canton de Genève (ci-après: le Grand Conseil), le Conseil d'Etat a conclu à la soumission de l'initiative au vote du peuple en dépit d'importants problèmes de conformité au droit supérieur, en vertu du principe "in dubio pro populo". Il a invité le Grand Conseil à rejeter l'initiative sans lui opposer de contre-projet direct. Par décision du 12 juin 2009, publiée dans la Feuille d'avis officielle le 17 juin 2009, le Grand Conseil, suivant l'avis de la Commission législative, a considéré que l'initiative n'était pas conforme au droit supérieur; il a refusé d'invalider partiellement l'initiative et l'a déclarée totalement invalide par 49 voix contre 30. B. Agissant par la voie du recours en matière de droit public, l'association SolidaritéS ainsi que Pierre Vanek, Jocelyne Haller, Gilles Godinat et Andrée Jelk-Peila, tous citoyens genevois, demandent au Tribunal fédéral d'annuler cette décision et de constater la validité de l'initiative. Le Grand Conseil conclut au rejet du recours. Un second échange d'écritures a eu lieu, au terme duquel les recourants persistent dans leurs conclusions.