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.

Considérant en droit:
1. 1.1 Dans la mesure où le litige porte sur l'octroi d'une dérogation à la condition de l'âge minimal pour commencer la scolarité, sans que cela soit lié à l'évaluation des capacités, il échappe à la clause d'exclusion de l'art. 83 let. t LTF. La voie du recours en matière de droit public est donc ouverte. Les autres conditions de recevabilité étant réunies, il convient en principe d'entrer en matière.
1.2 Le Tribunal fédéral est habilité à examiner la bonne application du droit concordataire (intercantonal; art. 95 let. e LTF), mais non celle du droit cantonal. S'agissant de ce dernier, il peut seulement revoir l'éventuelle contrariété de l'interprétation et de l'application des normes cantonales avec les dispositions énumérées à l'<ref-law>, soit en particulier, en l'espèce, avec le droit constitutionnel fédéral. Encore faut-il que les violations alléguées du droit constitutionnel soient exposées de manière précise, à défaut de quoi le Tribunal de céans n'entre pas en matière à leur sujet. Il en va de même des atteintes que l'interprétation et l'application du droit cantonal auraient causées au droit intercantonal (<ref-law>).
1.3 La conclusion en constatation de la violation des art. 19 Cst. et 13 Pacte ONU I est irrecevable. Elle est en effet subsidiaire et n'a aucune portée propre par rapport à celle tendant à l'annulation de l'arrêt entrepris.
1.4 La production de moyens de preuve nouveaux est exclue devant le Tribunal fédéral (<ref-law>), sauf exceptions non réalisées en l'espèce. Le dépôt d'un avis de droit échappe à cette interdiction, dans la mesure où il s'agit d'un argumentaire juridique assimilé à de simples allégations de partie (<ref-ruling> consid. 3.4 p. 87 s.).
2. 2.1 Les recourants soulèvent d'abord un grief de nature formelle, à savoir la violation de l'interdiction du déni de justice formel (art. 29 al. 2 Cst.). Selon eux, l'autorité précédente n'aurait pas examiné le grief - expressément soulevé - tiré de l'absence de proportionnalité de la mesure en relation avec l'abus du pouvoir d'appréciation.
2.2 Le grief est manifestement infondé, dès lors que, au consid. 8 in fine de son arrêt, la Cour cantonale a expressément précisé que "[l]e DIP a ainsi refusé à juste titre d'entrer en matière sur la demande de dérogation et le texte légal clair ne lui laissait aucun pouvoir d'appréciation". Une telle motivation satisfait aux exigences de l'art. 29 al. 2 Cst.
3. Les recourants estiment que la Cour de justice a violé l'art. 48 al. 5 Cst. - faisant obligation aux cantons de respecter le droit intercantonal - en relation avec les art. 5 al. 1 HarmoS et 4 al. 2 de la convention scolaire romande du 21 juin 2007 (CSR; RS/GE C 1 07).
3.1 Comme l'a rappelé l'autorité précédente, HarmoS a pour but d'harmoniser la scolarité obligatoire au sein des cantons concordataires en accordant les objectifs de l'enseignement et les structures scolaires, d'une part, et, d'autre part, en développant et en assurant la qualité et la perméabilité du système scolaire au moyen d'instruments de pilotage communs (art. 1 HarmoS). Il prévoit notamment 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 (art. 5 al. 1 HarmoS). Les cantons s'engagent à respecter les caractéristiques structurelles de la scolarité obligatoire, telles que définies au chapitre III, dont l'art. 5 fait partie, dans un délai maximal de six ans après l'entrée en vigueur de l'accord. Selon l'art. 15 HarmoS, l'assemblée plénière de la CDIP décide de la date d'abrogation de l'art. 2 du concordat intercantonal du 29 octobre 1970 sur la coordination scolaire (CICS; RS/GE C 1 05), disposition qui prévoit notamment que l'âge d'entrée à l'école est fixé à 6 ans révolus au 30 juin, les cantons pouvant avancer ou retarder cette date dans une limite de quatre mois. Au 20 avril 2011, l'art. 2 CICS n'avait pas été abrogé (recueil des bases légales de la CDIP, qui peut être consulté à l'adresse http://www.cdip.ch/dyn/11703.php).
En même temps qu'HarmoS est entrée en vigueur la CSR, dont le but est notamment d'instituer et de renforcer l'espace romand de formation, en application d'HarmoS (art. 1 al. 1 CSR). Elle comporte des domaines dans lesquels la coopération entre les cantons est obligatoire et fait l'objet d'une réglementation contraignante sur certains points. Sur d'autres, la collaboration n'est pas obligatoire et donne lieu à des recommandations (art. 2 CSR). Le début de la scolarisation entre dans la première catégorie (art. 3 al. 1 let. a CSR). La convention prévoit que l'élève est scolarisé dès l'âge de 4 ans révolus, le jour déterminant étant le 31 juillet (art. 4 al. 1 CSR). La fixation du jour de référence n'exclut pas les cas de dérogations individuelles qui demeurent de la compétence des cantons (art. 4 al. 2 CSR).
3.2 Le contenu de la législation cantonale pertinente retenue par l'autorité précédente n'est pas remis en cause par les recourants. Il y a donc lieu de se référer aux indications figurant dans l'arrêt entrepris, le Tribunal fédéral n'appliquant pas le droit cantonal d'office.
3.2.1 Dans le canton de Genève, la durée de la scolarité obligatoire est réglée à l'art. 11 de la loi sur l'instruction publique du 6 novembre 1940 (LIP; RS/GE C 1 10). Cette disposition légale a été modifiée le 10 juin 2011, modification qui est entrée en vigueur le 29 août 2011. Dans son ancienne teneur, l'art. 11 al. 1 prévoyait que la scolarité obligatoire comprenait neuf années scolaires complètes. Les enfants âgés de 6 ans révolus y étaient astreints dès le début de l'année scolaire; ils achevaient leur scolarité obligatoire à la fin de l'année scolaire au cours de laquelle ils avaient atteint l'âge de 15 ans révolus. L'école enfantine, quant à elle, comprenait des classes facultatives destinées aux enfants de 4 et 5 ans (ancien art. 24 LIP).
Sur la base d'une délégation contenue dans l'ancien art. 11 al. 1 LIP, le Conseil d'Etat avait édicté le règlement relatif aux dispenses d'âge du 12 juin 1974 (abrogé avec effet au 29 décembre 2011; ci-après: aRDAge), dont l'art. 1 prévoyait ce qui suit:
"L'âge d'entrée à l'école obligatoire est fixé à 6 ans révolus au 30 juin. Par voie de conséquence, les enfants qui atteignent:
a) l'âge de 6 ans révolus au 30 juin sont astreints à la scolarité obligatoire et doivent entrer en 1ère année primaire dès le début de l'année scolaire;
b) l'âge de 5 ans révolus au 30 juin peuvent être admis dans la 2ème classe facultative de la division enfantine;
c) l'âge de 4 ans révolus au 30 juin peuvent être admis dans la 1ère classe
facultative de la division enfantine."
L'aRDAge disposait qu'en dérogation à la disposition précitée, des dispenses d'âge pouvaient être accordées aux élèves de l'enseignement public (art. 2 aRDAge). Pour les élèves entrant en première année de l'enseignement enfantin, l'art. 3 aRDAge, intitulé "Dispenses simples - modalités transitoires" prévoyait qu'au moment de l'inscription, et sauf demande contraire des parents, une dispense d'âge simple était accordée spontanément à la rentrée 2010 pour les élèves entrant en 1ère` classe enfantine nés jusqu'au 30 septembre 2006 et, à la rentrée 2011, pour les élèves entrant en 1ère classe enfantine nés jusqu'au 31 août 2007 (art. 3 al. 1 let. a et b aRDAge). Cette disposition tendait à atténuer l'impact du passage du système actuel instauré par le CICS, permettant d'avancer ou de reculer de quatre mois la date de référence, au système HarmoS qui instaurait une date de référence contraignante (exposé des motifs à l'appui du projet de loi autorisant le Conseil d'Etat à adhérer à HarmoS [projet de loi 10350], p. 11). L'alinéa 2 de cette disposition précisait que, dès la rentrée 2012, tous les enfants âgés de 4 ans révolus au 31 juillet devaient être scolarisés en 1ère classe enfantine.
Contrairement à la dispense d'une année ou plus prévue à l'art. 4 aRDAge, qui pouvait être accordée à un enfant en âge de fréquenter la 2ème enfantine jugé apte, du point de vue psychopédagogique et médical, à suivre sans difficultés une classe de 1ère primaire à l'issue d'une procédure engagée par une demande écrite et motivée des parents, la dispense d'âge simple présentait un caractère automatique.
L'aRDAge ne prévoyait pas d'autres cas de dispense d'âge que ceux susmentionnés. En particulier, il ne permettait plus d'octroyer des dispenses d'âge simples pour des enfants nés respectivement après le 30 septembre 2006 pour la rentrée 2010, après le 31 août 2007 pour la rentrée 2011 et après le 31 juillet 2008 pour la rentrée 2012. A partir de la rentrée 2013-2014, la dispense d'âge simple était totalement supprimée et la nouvelle date de référence pour l'entrée à l'école primaire publique était le 31 juillet à 4 ans. Le règlement ne contenait pas de clause réservant la possibilité de dérogations dans des situations exceptionnelles.
3.2.2 Dans sa nouvelle teneur du 10 juin 2011, l'art. 11 LIP dispose ce qui suit:
"1 La scolarité est obligatoire pour les enfants dès l'âge de 4 ans révolus au 31 juillet.
2 L'âge d'entrée à l'école obligatoire ne peut être avancé.
3 Le Conseil d'Etat définit dans le règlement les conditions auxquelles une dispense d'âge peut être accordée à des enfants qui, arrivés au terme de la première année du cycle élémentaire, sont jugés aptes du point de vue scolaire, psychologique et médical à fréquenter une classe destinée normalement à des élèves plus âgés.
4 Sur demande des parents et sous leur responsabilité, le département peut, exceptionnellement et pour de justes motifs, retarder d'une année scolaire l'entrée d'un élève à l'école obligatoire."
L'art. 21 LIP ne distingue plus l'école enfantine de l'école primaire et l'ancien art. 24 LIP a été abrogé.
L'aRDAge a été abrogé et remplacé par le règlement du Conseil d'Etat relatif aux dispenses d'âge du 21 décembre 2011 (RDAge; RS/GE C 1 10.18), lequel ne contient plus aucune disposition traitant des dispenses simples accordées au début de l'enseignement obligatoire.
3.3 L'autorité précédente a tranché la contestation sur la base du droit en vigueur lors du prononcé de la décision de première instance, soit au regard des dispositions d'HarmoS, de la CSR, de la LIP dans sa teneur antérieure à la novelle du 10 juin 2011, ainsi que de l'aRDAge. Les recourants ne critiquent pas la décision entreprise sur ce point. Ils estiment en revanche que l'art. 4 al. 2 CSR fait obligation aux cantons de prévoir un régime de dérogation et donc de mettre en place la procédure permettant d'accorder de telles dérogations. Leur argumentation y relative ne correspond toutefois pas aux exigences de motivation de l'<ref-law>, dans la mesure où ils se bornent à affirmer l'existence d'un tel régime, sans démontrer en quoi l'interprétation que la Cour cantonale a faite de cette disposition serait erronée. Quoi qu'il en soit, la question de la recevabilité dudit grief peut demeurer indécise, du moment que celui-ci doit de toute manière être rejeté, pour les motifs suivants.
3.4 L'enfant C._ est né le 7 août 2008. Il est donc soumis au régime d'admission à l'école prévu par les art. 5 al. 1 HarmoS, 4 al. 1 CSR et 1 let. c aRDAge. Contrairement à ce que pensent les recourants, l'art. 4 al. 2 CSR ne fonde aucunement un droit à l'examen d'une dérogation. Le texte de la norme se borne en effet à confirmer que la fixation du jour de référence n'exclut pas les cas de dérogations individuelles "qui demeurent de la compétence des cantons". Cette disposition conventionnelle accorde la compétence aux cantons qui le désirent de permettre des dérogations, mais ne leur fait pas obligation d'instaurer un tel régime, cette question relevant de leur autonomie législative spécifiquement garantie par l'art. 62 Cst. et qu'ils n'ont pas restreinte par voie conventionnelle. Dans ces conditions, l'option prise par les autorités cantonales d'imposer, dès la rentrée scolaire 2012, un respect strict de la condition de l'âge est conforme tant au texte concordataire qu'à celui de la CSR. Les recourants ne démontrent nullement, en utilisant les méthodes d'interprétation usuelles, en quoi la Cour de justice n'aurait pas dû s'en tenir à la lettre claire de l'art. 4 al. 2 CSR. Leur grief doit donc être rejeté.
4. Les recourants se plaignent de violation des art. 19 Cst. et 13 al. 2 let. a du Pacte ONU I. Dans la mesure où, sous certaines exceptions non concernées par la présente cause, les dispositions du Pacte ONU I ne sont pas directement justiciables (<ref-ruling> consid. 2 et 3 p. 241 ss), le grief soulevé ne sera traité qu'au regard des garanties offertes par l'art. 19 Cst. Cette dernière disposition ainsi que l'art. 62 Cst. ont été concrétisés par la législation genevoise, dont le Tribunal fédéral revoit l'interprétation et l'application en se limitant en principe à l'arbitraire (art. 9 Cst.). Le Tribunal de céans examine en revanche librement si le droit cantonal et son application sont conformes aux garanties constitutionnelles (<ref-ruling> consid. 2 p. 319 avec références).
4.1 L'art. 19 Cst. garantit à chacun le droit à un enseignement de base suffisant et gratuit. En vertu de ce droit social, les cantons sont obligés d'offrir à tout enfant la possibilité de suivre un enseignement obligatoire, suffisant et gratuit, de manière à assurer son développement personnel (<ref-ruling> consid. 3.1 p. 158; <ref-ruling> consid. 7.3 p. 38; voir aussi récemment arrêt 2C_971/2011 du 13 avril 2012 consid. 3.1). Ils restent cependant compétents pour réglementer du début à la fin la scolarité obligatoire, leur seule obligation étant de ne pas par trop raccourcir ou prolonger la durée de celle-ci (A. Auer/G. Malinverni/M. Hottelier, Droit constitutionnel suisse, vol. II, 2ème éd., 2006, ch. 1540, p. 687 s.). Il est du reste admis que l'art. 19 Cst. ne fait pas obstacle à la fixation schématique du début de la scolarité obligatoire (J. P. MÜLLER/M. SCHEFER, Grundrechte in der Schweiz, 4ème éd., 2008, p. 784). Au surplus, en affirmant que l'enseignement de base doit être suffisant, l'art. 19 Cst. recourt à une notion juridique indéterminée qui laisse aux cantons une certaine marge d'appréciation (<ref-ruling> consid. 3.1 p. 158; <ref-ruling> consid. 3.2 p. 354, arrêt 2C_971/2011, précité, consid. 3.2). Le droit constitutionnel à un enseignement de base gratuit et suffisant n'implique d'ailleurs pas que chaque enfant puisse prétendre à un enseignement optimal, ni à celui qui lui serait le plus approprié (arrêts 2C_971/2011, précité, consid. 3.2; 2C_446/2010 du 16 septembre 2010 consid. 5.2).
La jurisprudence n'a pas tranché la question de savoir en fonction de quelles normes et de quels principes (art. 5 ou 36 Cst.) le droit social garanti par l'art. 19 Cst. pouvait être restreint (arrêt 2C_446/2010, précité, consid. 5.3 et les références à la jurisprudence et à la doctrine). En effet, les conséquences juridiques des différentes théories soutenues ne diffèrent que dans une faible mesure, dès lors que toute atteinte à un tel droit doit être fondée sur la loi, être justifiée par l'intérêt public et demeurer proportionnée.
4.2 En l'espèce, les recourants n'exposent nullement en quoi le droit cantonal adopté - partiellement en application du droit concordataire - violerait le droit garanti par l'art. 19 Cst., ni en quoi le canton de Genève, en édictant sa législation spécifique à dite matière, aurait excédé la marge d'appréciation que lui laissent les art. 19 et 62 Cst. A cela s'ajoute qu'ils n'expliquent pas en quoi le schématisme incontestable lié à la fixation d'un âge minimal pour débuter le cursus scolaire serait contraire au droit constitutionnel. Ils se bornent plutôt, sur un mode appellatoire et donc de manière irrecevable (cf. <ref-law>), à affirmer que la décision entreprise "retarde son [celui de C._] cursus scolaire, universitaire et professionnel d'une année, sans évoquer les conséquences financières pour les parents (crèche ou école privée pendant une année)".
Le fait que l'enfant C._ n'aura certes pas atteint l'âge minimal de quatre ans le 31 juillet 2012, mais bien au moment de la rentrée scolaire, ne suffit pas à démontrer que le droit constitutionnel aurait été violé par l'autorité précédente. En tout cas, une telle situation n'a rien d'insoutenable et ne fait pas apparaître le droit cantonal comme arbitraire, ce que les recourants ne prétendent d'ailleurs pas.
En tant que recevable, le grief de violation de l'art. 19 Cst. doit donc être rejeté.
5. Les recourants se plaignent d'inégalité par rapport aux enfants de 4 ans nés avant le 31 juillet.
5.1 La protection de l'égalité (art. 8 Cst.) et celle contre l'arbitraire (art. 9 Cst.) sont étroitement liées. Une disposition viole le principe d'égalité lorsqu'elle établit des distinctions juridiques qui ne se justifient par aucun motif raisonnable au regard de la situation de fait à réglementer ou lorsqu'elle omet de faire des distinctions qui s'imposent au vu des circonstances, c'est-à-dire lorsque ce qui est semblable n'est pas traité de manière identique et ce qui est dissemblable ne l'est pas de manière différente; cela suppose que le traitement différent ou semblable injustifié se rapporte à une situation de fait importante (<ref-ruling> consid. 5.3 p. 125; <ref-ruling> consid. 6.2 p. 137; <ref-ruling> consid. 3 p. 382 s.). Dans ce cadre, le législateur dispose toutefois d'un large pouvoir d'appréciation et le Tribunal fédéral ne peut intervenir que si, sur des points importants, les assimilations ou distinctions effectuées s'avèrent clairement injustifiées et insoutenables; dans cette mesure, le grief d'inégalité se confond pour l'essentiel avec celui d'arbitraire (ATF <ref-ruling> consid. 6.2 p. 137; <ref-ruling> consid. 4.2 p. 6, 313 consid. 3.2 p. 317; <ref-ruling> consid. 5 p. 192).
5.2 En l'espèce, les règles harmonisant le système scolaire obligatoire résultant d'HarmoS pour déterminer la durée de l'enseignement obligatoire en années sont fixées en fonction d'un âge minimum requis. Le début d'année scolaire étant fixé en cours d'année civile, cela imposait d'arrêter une date limite à partir de laquelle les enfants nés dans l'année civile ne peuvent plus être admis pour l'année scolaire considérée. En l'occurrence, le législateur a retenu le 31 juillet de l'année civile (art. 5 al. 1 HarmoS, art. 4 al. 1 CSR, art. 3 al. 2 aRDAge), date qui précède d'environ un mois la date de la rentrée scolaire effective, laquelle est sujette à variation. Dès lors que tous les enfants de quatre ans nés avant cette date ont le droit d'être scolarisés et que ceux nés après ne peuvent y prétendre, les enfants de chacune des catégories concernées sont traités de manière identique et le principe d'égalité est respecté.
Pour le reste, comme le Département cantonal le relève avec pertinence dans sa détermination, le régime proposé par les recourants serait précisément susceptible de créer des inégalités, d'une rentrée et d'un canton à l'autre. En premier lieu, les dates de rentrée scolaire fluctuent. Pour le canton de Genève, la rentrée scolaire est fixée au 29 août 2012, celle de 2013 au 26 août. Un enfant né le 27 août 2008 pourrait ainsi, selon la théorie développée par les recourants, commencer l'école en 2012, alors que celui né le 27 août 2009 ne le pourrait en 2013, puisqu'il n'aurait pas atteint l'âge de 4 ans au jour de la rentrée. Ensuite, le but d'harmonisation ne serait nullement atteint en prenant en compte l'âge effectif au jour de la rentrée scolaire, du moment que celui-ci peut encore varier d'un canton à l'autre. Les enfants des différents cantons seraient ainsi traités de manière inégale, ce qui serait contraire aux objectifs concordataires.
Au vu de ce qui précède, le grief d'inégalité est mal fondé.
6. En tant que recevable, le recours doit donc être rejeté. Succombant, les recourants en supporteront les frais, solidairement entre eux (cf. art. 66 al. 1 et 5 LTF). Il n'est pas alloué de dépens (cf. art. 68 al. 2 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge des recourants, solidairement entre eux.
3. Le présent arrêt est communiqué au mandataire des recourants, au Département de l'instruction publique, de la culture et du sport, et à la Cour de justice du canton de Genève, Chambre administrative, 2ème section.
Lausanne, le 26 juillet 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Vianin