Faits: A. Les époux A._ et B._ sont les parents de C._, né le 7 août 2008. Ils sont domiciliés dans le canton de Genève. Au mois de décembre 2009, la Direction générale de l'enseignement primaire du Département de l'instruction publique, de la culture et du sport du canton de Genève (ci-après: le Département cantonal) a écrit à l'ensemble des parents concernés pour les informer de la mise en oeuvre de l'accord intercantonal sur l'harmonisation de la scolarité obligatoire du 14 juin 2007, entré en vigueur le 1er août 2009 (HarmoS; RS/GE C 1 06). L'art. 5 al. 1 de ce dernier prévoyait que "l'élève est scolarisé dès l'âge de 4 ans révolus (le jour de référence étant le 31 juillet)". La mesure serait introduite progressivement, de la façon suivante: à la rentrée 2010, la dispense d'âge simple serait accordée aux enfants nés avant le 30 septembre 2006; à la rentrée 2011, les enfants nés le 31 août 2007 ou antérieurement pourraient entrer en 1ère enfantine; dès la rentrée 2012, application d'HarmoS, avec obligation scolaire à 4 ans et le 31 juillet comme date butoir pour tous les élèves de 1ère enfantine; à partir de la rentrée 2013-2014, la dispense d'âge simple serait totalement supprimée et la date de référence pour l'entrée à l'école primaire publique serait le 31 juillet. Le 18 mars 2011, les époux A.B._ ont écrit à la Direction générale de l'enseignement primaire du Département cantonal. Ils souhaitaient que leur fils C._ bénéficie d'une dérogation à la règle qui lui imposerait de ne commencer l'école qu'à la rentrée 2013. La date de référence aurait pour effet que leur enfant, né le 7 août 2008, manquerait de quelques jours la date butoir du 31 juillet pour débuter sa scolarité en août 2012 et qu'il devrait attendre une année pour commencer l'école à cinq ans révolus, en août 2013. Selon eux, HarmoS n'excluait pas les dérogations individuelles, qui demeuraient de la compétence des cantons. Par décision du 24 mars 2011, le Département cantonal a rejeté la demande de dérogation. A l'encontre de ce prononcé, les époux A.B._ ont recouru à la Chambre administrative de la Cour de justice du canton de Genève, qui les a déboutés par arrêt du 17 avril 2012. B. Les époux A.B._ forment un recours en matière de droit public contre le jugement de la Cour de justice du 17 avril 2012. Ils requièrent l'annulation de cet arrêt et sa réforme en ce sens que l'enfant C._ est autorisé à débuter sa scolarité lors de la rentrée 2012 dans le canton de Genève. Ils concluent aussi à la constatation d'une violation des art. 19 Cst. et 13 du Pacte international du 16 décembre 1966 relatif aux droits économiques, sociaux et culturels (Pacte ONU I; RS 0.103.1). Appelés à se déterminer sur le recours, la Cour de justice a déclaré persister dans les considérants et le dispositif de son arrêt, alors que le Département cantonal a conclu à son rejet sous suite de frais et dépens. Ce dernier a joint à sa détermination un avis de droit de l'Institut du fédéralisme de l'Université de Fribourg. Les recourants ont répliqué par écriture datée du 3 juillet 2012. 