Sachverhalt:
A. Y._ wurde im Jahr 1992 geboren. Er besuchte zuletzt ein Gymnasium in Deutschland, ehe er zu Beginn des Schuljahrs 2008/2009 in die vierte Klasse des Gymnasiums A._ in Basel eintrat. Aufgrund nicht erfüllter Promotionsvoraussetzungen verfügte das Gymnasium A._ die Remotion, worauf Y._ im Schuljahr 2009/2010 die vierte Gymnasialklasse wiederholte. Wenngleich die Leistungen keine Promotion zugelassen hätten, wurde ihm im Sinne einer Ausnahme ermöglicht, in die fünfte, letzte Gymnasialklasse des Schuljahres 2010/2011 überzutreten. Begründet wurde dies im Wesentlichen damit, dass der Schüler aus dem Ausland zugezogen sei und über ein Defizit im Bereich des Französisch verfüge. Die ausnahmsweise Promotion wurde an die Bedingung geknüpft, dass die eigens angesetzte ausserordentliche Probezeit, ein Semester, erfolgreich bestanden werde. Y._ schloss das erste Semester des fünften Gymnasialjahres mit vier ungenügenden Noten ab ("Biologie und Chemie", "Französisch", "Mathematik", "Wirtschaft und Recht"). Mit Blick darauf und auf die fehlende Möglichkeit einer Repetition des zweiten Semesters der vierten Gymnasialklasse ordnete das Gymnasium A._ die Wegweisung von der Schule an, worauf Y._ die Schule am 21. Januar 2011 verliess.
B. Die Eltern des Schülers bemühten sich in der Folge um den Eintritt ihres Sohnes in das Gymnasium B._, was dessen Rektor zunächst zustimmend beantwortete (Aufnahme in die vierte Gymnasialklasse), letztlich aber am 23. Februar 2011 mit Blick auf die Vorgeschichte verwarf. Dem vorübergehenden Besuch des Unterrichts in der vierten Klasse, freilich als Hospitant bis zum Übertritt in eine andere Ausbildung, stehe, so der Rektor, aber nichts entgegen.
C. X._, der Vater des Schülers, gelangte am 28. Februar 2011 an das Erziehungsdepartement des Kantons Basel-Stadt und beantragte die Zulassung seines Sohnes zur Repetition der fünften Gymnasialklasse, dies ab Sommer 2011 und nunmehr am Gymnasium B._. Der Leiter der Dienststelle "Weiterführende Schulen" des Erziehungsdepartements bestätigte in seiner Verfügung vom 29. Juni 2011 den Standpunkt, welchen die Rektorin des Gymnasiums A._ eingenommen hatte. Danach sei eine weitere Repetition nicht vorgesehen, sodass keine Möglichkeit bestehe, die Ausbildung fortzusetzen und an einem staatlichen oder privaten Gymnasium im Kanton Basel-Stadt zur Maturitätsprüfung zu gelangen. Eine dagegen gerichtete Beschwerde vom 25. Juli 2011 wies das Erziehungsdepartement des Kantons Basel-Stadt am 28. September 2011 ab, ebenso wie das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, das am 15. Februar 2012 den Rekurs vom 4. Oktober/30. November 2011 beurteilte.
D. Gegen dieses Urteil erheben X._ (Beschwerdeführer 1) und Y._ (Beschwerdeführer 2) mit Eingabe vom 23. März 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragen, das angefochtene Urteil des Appellationsgerichts des Kantons Basel-Stadt sei aufzuheben, und es sei das Erziehungsdepartement des Kantons Basel-Stadt anzuweisen, den Beschwerdeführer 2 "zur fünften Klasse bzw. zu den Maturitätsprüfungen im Gymnasium B._ zuzulassen". Überdies sei der Beschwerde die aufschiebende Wirkung zuzuerkennen. Das Appellationsgericht und das Erziehungsdepartement beantragen die Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid in einer Materie des öffentlichen Rechts, der an sich mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht weitergezogen werden kann (Art. 82 lit. a, 86 Abs. 1 lit. d und Abs. 2, 90 BGG).
Gemäss Art. 83 lit. t BGG ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten unzulässig gegen Entscheide über das Ergebnis von Prüfungen und anderen Fähigkeitsbewertungen, namentlich auf den Gebieten der Schule, der Weiterbildung und der Berufsausübung. Praxisgemäss bleibt die Ausnahme wirkungslos bei Entscheiden im Zusammenhang mit Prüfungen, die sich nicht auf die Beurteilung einer Leistung oder einer sonstigen Befähigung beziehen, sondern namentlich organisatorischer Natur sind. Ob der Ausschlussgrund zur Anwendung kommt, hängt vom Gegenstand des angefochtenen Entscheids und nicht vom Inhalt der erhobenen Rügen ab (<ref-ruling> E. 1.1 S. 44; <ref-ruling> E. 1 S. 231; <ref-ruling> E. 1.1.1 S. 63; Urteile 2D_5/2012 vom 19. April 2012 E. 1.1; 2D_10/2011 vom 15. Juni 2011 E. 1.1; 2D_76/2009 vom 14. Mai 2010 E. 1; 2C_577/2009 vom 6. Januar 2010 E. 1.1). Ausgeschlossen ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten beispielsweise, wenn das Nichtbestehen der Maturitätsprüfung angefochten werden soll (Urteil 2D_28/2011 vom 7. Juni 2011), ebenso gegen Entscheide über den Ausschluss aus einer Schule oder einem Lehrgang, die auf einer Leistungsbeurteilung beruhen (Urteile 2C_579/2010 vom 17. November 2010 E. 1.1; 2D_77/2009 vom 26. April 2010 E. 1.1; 2D_142/2008 vom 23. April 2009 E. 1.2), generell alle Entscheide, die sich auf eine Bewertung der intellektuellen oder physischen Fähigkeiten oder die Eignung eines Kandidaten beziehen (<ref-ruling> E.1.1 S. 44).
Vorliegend geht es um die Zulassung zur fünften Gymnasialklasse bzw. zur Maturitätsprüfung. Dabei steht nicht die - als solche unbestrittene - Leistungsbeurteilung zur Diskussion, sondern die Frage, ob auf Grund der massgebenden Rechtsgrundlagen mit diesen Leistungen ein Anspruch auf die Zulassung zur fünften Gymnasialklasse und zur Maturitätsprüfung besteht. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist damit zulässig. Die übrigen Eintretensvoraussetzungen geben zu keinen Bemerkungen Anlass, sodass unter Vorbehalt des Nachfolgenden auf die Beschwerde einzutreten ist.
1.2 Mit der Beschwerde kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. Soweit, wie im vorliegenden Fall, die Anwendung kantonalen (Gesetzes-)Rechts gerügt wird, kann im Wesentlichen geltend gemacht werden, der angefochtene Entscheid verstosse gegen Bundesrecht (<ref-law>), hier namentlich gegen die verfassungsmässigen Rechte und Grundsätze mit Einschluss des Willkürverbots (<ref-ruling> E. 1.2 S. 145; <ref-ruling> E. 3 S. 351). Die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht prüft das Bundesgericht nur unter Rüge- und Begründungsvorbehalt (<ref-law>; <ref-ruling> E. 1.4.2 S. 254; zum Ganzen Urteil 2C_705/2011 vom 26. April 2012 E. 1.6). Der Grundsatz der Rechtsanwendung von Amtes wegen im Sinne von <ref-law> gilt insofern nicht. Die bundesgerichtliche Praxis verlangt, dass die Verfassungsverletzung "klar und detailliert anhand der Erwägungen des angefochtenen Entscheids" dargelegt wird (<ref-ruling> E. 6 S. 397, mit Hinweisen). Auf rein appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling> E. 2.8 S. 494 mit Hinweisen).
Inwiefern die Beschwerde dem qualifizierten Rügeerfordernis entspricht und sich hinreichend mit der Frage nach Bestand und Verletzung verfassungsmässiger Rechte auseinandersetzt, ist zumindest fraglich. Dies kann freilich offenbleiben, nachdem sich das Rechtsmittel in der Sache selbst ohnehin als unbegründet erweist.
1.3 In tatsächlicher Hinsicht legt das Bundesgericht seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Deren Sachverhaltsfeststellungen können nur berichtigt werden, sofern sie offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (Art. 105 Abs. 2). Dies ist dann der Fall, wenn der Sachverhalt willkürlich ermittelt worden (<ref-law>) oder dessen Feststellung unter Verletzung verfassungsmässiger Rechte und Grundsätze zustande gekommen ist (<ref-ruling> E. 8.1 S. 153). Zudem muss aufgezeigt werden, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
2. Die beiden Beschwerdeführer rügen zunächst die Feststellung des Sachverhalts (dazu E. 3 hienach). Sodann beanstanden sie die Anwendung des massgebenden kantonalen Rechts, die sie als willkürlich erachten (E. 4), erblicken im Verhalten der kantonalen Behörden eine Verletzung des Grundsatzes von Treu und Glauben (E. 5) und eine willkürliche Rechtsverzögerung (E. 6). Schliesslich tragen sie eine Verletzung des kantonalen Grundrechts auf Bildung vor (E. 7).
3. In tatsächlicher Hinsicht bringen die Beschwerdeführer vor, die Vorinstanz spreche zu Unrecht davon, der Beschwerdeführer 1 habe beim Gymnasium B._ um Aufnahme seines Sohnes in die vierte - und mithin nicht in die fünfte - Klasse ersucht. In Wahrheit habe er sich um die Zulassung des Beschwerdeführers 2 in die Maturitätsklasse bemüht. Mit dem vorliegenden Rechtsmittel versuchen die Beschwerdeführer zu erreichen, dass der Beschwerdeführer 2 in die fünfte Klasse des Gymnasiums B._ aufgenommen wird. Für die hienach vorzunehmende Beurteilung bleibt die gerügte Verwechslung ohne Belang, weshalb der Einwand nicht zu hören ist (vorne, E. 1.3).
4. 4.1 Im Bildungsrecht des Kantons Basel-Stadt stehen sich zwei Verordnungen gegenüber, die hier von Bedeutung sind. Zum einen handelt es sich um die Verordnung vom 23. Januar 1996 über die Zeugnisse, die Promotionen und Remotionen sowie die Lernberichte an den Gymnasien Basel-Stadt (LBVG/BS; SG 413.810), welche Teile der gymnasialen Ausbildung bis zur Maturitätsprüfung zum Gegenstand hat. Zum andern ist die Verordnung vom 28. März 2000 betreffend die Maturitätsprüfungen im Kanton Basel-Stadt (MPV/BS; SG 413.820) zu berücksichtigen, aus welcher die Modalitäten von Zulassung zur und Ablauf der Prüfung hervorgehen.
4.2 Von einer Gymnasialklasse in die nächste befördert werden Schülerinnen und Schüler, die "von den Bestimmungen der §§ 5-7 nicht betroffen sind" (§ 4 Abs. 1 LBVG/BS). Während die §§ 5 und 6 die Remotion in der ersten Klasse betreffen, befasst sich § 7 LBVG/BS mit der Remotion in den zweiten bis vierten Klassen. Nach abgeschlossener Klassenwiederholung müssen bis zu Beginn einer weiteren Klassenwiederholung mindestens zwei Jahre verstreichen (§ 18 Satz 1 LBVG/BS), was auch bei einer freiwilligen Klassenwiederholung gilt (§ 18 Satz 2). Der Antrag auf freiwillige Klassenwiederholung kann in der zweiten bis fünften Klasse gestellt werden (§ 18a Abs. 2 Satz 1 LBVG/BS). Fehlt es an den Voraussetzungen für die Promotion von einer Klasse in die nächste, erlaubt § 9 Abs. 1 LBVG/BS im Sinne einer Billigkeitslösung den Verzicht auf die Remotion, falls die Leistungen der Schülerin oder des Schülers durch "unregelmässige Vorbildung, längere Krankheit oder ungünstige häusliche Verhältnisse so beeinträchtigt worden sind, dass ihnen in einzelnen Fächern keine oder keine genügenden Noten erteilt werden können". Eine derartige [ausserordentliche] Promotion kann mit einer ausserordentlichen Probezeit verbunden werden, wobei die Zeugnisklassenkonferenz "unter sinngemässer Anwendung der §§ 3-7 [entscheidet], ob die ausserordentliche Probezeit bestanden ist oder nicht". Schliesslich ordnet § 24 Abs. 4 MPV/BS an, dass in der fünften Klasse "eine freiwillige Repetition nach den Herbstferien als erster gescheiterter Versuch [gelte], die Maturität zu erlangen".
4.2 Von einer Gymnasialklasse in die nächste befördert werden Schülerinnen und Schüler, die "von den Bestimmungen der §§ 5-7 nicht betroffen sind" (§ 4 Abs. 1 LBVG/BS). Während die §§ 5 und 6 die Remotion in der ersten Klasse betreffen, befasst sich § 7 LBVG/BS mit der Remotion in den zweiten bis vierten Klassen. Nach abgeschlossener Klassenwiederholung müssen bis zu Beginn einer weiteren Klassenwiederholung mindestens zwei Jahre verstreichen (§ 18 Satz 1 LBVG/BS), was auch bei einer freiwilligen Klassenwiederholung gilt (§ 18 Satz 2). Der Antrag auf freiwillige Klassenwiederholung kann in der zweiten bis fünften Klasse gestellt werden (§ 18a Abs. 2 Satz 1 LBVG/BS). Fehlt es an den Voraussetzungen für die Promotion von einer Klasse in die nächste, erlaubt § 9 Abs. 1 LBVG/BS im Sinne einer Billigkeitslösung den Verzicht auf die Remotion, falls die Leistungen der Schülerin oder des Schülers durch "unregelmässige Vorbildung, längere Krankheit oder ungünstige häusliche Verhältnisse so beeinträchtigt worden sind, dass ihnen in einzelnen Fächern keine oder keine genügenden Noten erteilt werden können". Eine derartige [ausserordentliche] Promotion kann mit einer ausserordentlichen Probezeit verbunden werden, wobei die Zeugnisklassenkonferenz "unter sinngemässer Anwendung der §§ 3-7 [entscheidet], ob die ausserordentliche Probezeit bestanden ist oder nicht". Schliesslich ordnet § 24 Abs. 4 MPV/BS an, dass in der fünften Klasse "eine freiwillige Repetition nach den Herbstferien als erster gescheiterter Versuch [gelte], die Maturität zu erlangen".
4.3 4.3.1 Die Vorinstanz anerkennt, dass die §§ 5-7 LBVG/BS an sich nur die Remotion in der ersten bis und mit vierten Klasse regeln. Aufgrund von § 9 Abs. 3 LBVG/BS, der die Möglichkeit einer ausserordentlichen Probezeit schafft und welcher auf die §§ 3-7 dieser Verordnung verweist, hält sie eine Remotion auch in der Abschlussklasse für möglich. Aus Wortlaut und Systematik schliesst sie weiter auf die Anwendbarkeit von § 18 LBVG/BS, weswegen die Zwei-Jahres-Frist auch im Fall der Remotion aus der fünften Klasse zu berücksichtigen sei. Nichts anderes ergebe sich aus der MPV/BS, qualifiziere der Vorgang doch als "Nichtbestehen der Probezeit" (§ 9 Abs. 3 LBVG/BS), nicht jedoch als "freiwillige Repetition" (§ 24 Abs. 1 MPV/BS).
4.3.2 Die Beschwerdeführer stellen sich auf den Standpunkt, die im vorliegenden Fall geübte Praxis - [ausserordentliche] Beförderung eines Schülers in die fünfte Gymnasialklasse unter Remotion bei Nichtbestehen der [ausserordentlichen] Probezeit - sei im Verordnungsrecht nicht vorgesehen. Bei zutreffender Auslegung gebe es einzig zwei Alternativen. Entweder verbleibe der Schüler bis zur Maturitätsprüfung in der fünften Klasse und könne die Prüfung, sofern nicht bestanden, einmalig wiederholen (§ 24 Abs. 1 MPV/BS). Oder er entschliesse sich zur freiwilligen Repetition der fünften Klasse, was mit sich bringe, dass er nur einmal zur Maturitätsprüfung zugelassen werde (§ 24 Abs. 4 MPV/BS). Der im vorliegenden Fall eingeschlagene Weg - Remotion selbst noch in der fünften Klasse, Anwendung der Zwei-Jahres-Regel (§ 18 Satz 1 LBVG/BS) - entbehre einer rechtlichen Grundlage und beruhe insofern auf willkürlicher Rechtsanwendung, als § 9 Abs. 3 in Verbindung mit §§ 5 ff. LBVG/BS in der fünften Klasse keine Remotion zulasse. Entfalle eine Rückversetzung, bleibe für die Anwendung der Zwei-Jahres-Regel kein Raum. Lückenfüllend sei § 24 MPV/BS heranzuziehen, weswegen die fünfte Klasse einmalig repetiert werden könne. Damit einher gehe die Möglichkeit, die misslungene Maturitätsprüfung einmalig zu wiederholen.
4.3.3 Das Erziehungsdepartement des Kantons Basel-Stadt wendet in seiner Vernehmlassung ein, aus § 9 Abs. 3 LBVG/BS folge zumindest mittelbar, dass eine Schülerin oder ein Schüler, welche bzw. welcher die Promotionsbedingungen am Ende der ausserordentlichen Probezeit nicht erfüllt, entweder repetieren oder aber den Ausbildungsgang verlassen müsse, soweit gemäss § 18 LBVG/BS eine Klassenwiederholung nicht mehr zulässig ist. Keinesfalls gehe es darum, die Laufbahn bis zur Maturitätsprüfung zu "garantieren", indem auf das Bestehen der ausserordentlichen Probezeit nichts ankomme. Überall dort, wo eine Klassenwiederholung nach den Bestimmungen der LBVG/BS in Frage stehe, sei die Zwei-Jahres-Regel einschlägig.
4.3.3 Das Erziehungsdepartement des Kantons Basel-Stadt wendet in seiner Vernehmlassung ein, aus § 9 Abs. 3 LBVG/BS folge zumindest mittelbar, dass eine Schülerin oder ein Schüler, welche bzw. welcher die Promotionsbedingungen am Ende der ausserordentlichen Probezeit nicht erfüllt, entweder repetieren oder aber den Ausbildungsgang verlassen müsse, soweit gemäss § 18 LBVG/BS eine Klassenwiederholung nicht mehr zulässig ist. Keinesfalls gehe es darum, die Laufbahn bis zur Maturitätsprüfung zu "garantieren", indem auf das Bestehen der ausserordentlichen Probezeit nichts ankomme. Überall dort, wo eine Klassenwiederholung nach den Bestimmungen der LBVG/BS in Frage stehe, sei die Zwei-Jahres-Regel einschlägig.
4.4 4.4.1 Unstreitig ist, dass der Beschwerdeführer 2 die Voraussetzungen zur [ordentlichen] Promotion in die fünfte Gymnasialklasse auch am Ende des Schuljahres 2009/2010 nicht erfüllte. Insofern wäre zu diesem Zeitpunkt eine Remotion angezeigt gewesen, wobei einer solchen die Zwei-Jahres-Frist im Sinne von § 18 Satz 1 LBVG/BS entgegengestanden wäre. Im Ergebnis wäre die Wegweisung von der Schule unvermeidlich gewesen. Mit Blick auf die Assimilierungsschwierigkeiten des Beschwerdeführers 2, der den ersten Teil seiner gymnasialen Ausbildung im Ausland absolviert hatte, sollte ihm freilich eine Art "letzte Chance" gewährt werden. Dass dem so war, kann den Beschwerdeführern nicht entgangen sein, war die [definitive] Zulassung zum fünften Gymnasialjahr doch ausdrücklich davon abhängig, dass die Probezeit bestanden werde. Die Beschwerdeführer beanstanden das gewählte Vorgehen erst, seit feststeht, dass die Probezeit nicht bestanden wurde.
4.4.2 Die beiden Rechtsverordnungen des kantonalen Rechts regeln je einen für sich abgeschlossenen Bereich. Hat die eine im Wesentlichen die Beförderung und Rückversetzung während der gymnasialen Ausbildung zum Gegenstand (LBVG/BS), betrifft die andere die Durchführung der Maturitätsprüfungen, die unter der Aufsicht des Kantons Basel-Stadt durchgeführt werden (so § 1 Abs. 1 MPV/BS). Insoweit ergibt sich in sachlicher und zeitlicher Hinsicht eine klare Abgrenzung. Überschneidungen liegen vor, soweit es um die freiwillige Wiederholung einer Gymnasialklasse geht. Die freiwillige Repetition setzt einen begründeten Antrag voraus, ist in der zweiten bis fünften Klasse möglich und unterliegt der Bewilligungspflicht seitens der Schulleitung, wobei die Zwei-Jahres-Regel vorgeht (§ 18 f. LBVG/BS). Erfolgt in der fünften Klasse eine freiwillige Repetition nach den Herbstferien, gilt dies als erster gescheiterter Versuch, die Maturität zu erlangen (§ 24 Abs. 3 MPV/BS).
4.4.3 Mit der Vorinstanz ist festzuhalten, dass die Voraussetzungen für eine freiwillige Repetition fehlten, womit eine Bezugnahme auf § 24 Abs. 3 MPV/BS entfällt. Die Vorinstanz durfte willkürfrei davon ausgehen, dass der Tatbestand der nichtbestandenen Probezeit gegeben sei. Geht es um die "freiwillige Wiederholung", setzt dies begrifflich voraus, dass die Gymnasiastin oder der Gymnasiast den Entscheid aus freien Stücken trifft, also die Ausbildung auch fortsetzen könnte, so sie dies wollte. Hatte der Beschwerdeführer 2 im Probesemester vier ungenügende Noten erzielt, stand ihm am Ende des ersten Semesters des fünften Jahres die Möglichkeit des ordentlichen Abschlusses des letzten Semesters nicht mehr offen. Damit bleibt es bei der ausschliesslichen Anwendbarkeit der Regeln der LBVG/BS und kann sich einzig fragen, ob eine Remotionsmöglichkeit auch im Abschlussjahr gegeben sei.
4.4.4 Die Vorinstanz bejaht dies mit Blick darauf, dass die Zeugnisklassenkonferenz aufgrund von § 9 Abs. 3 LBVG/BS am Ende der Probezeit "unter sinngemässer Anwendung der §§ 3-7" darüber zu befinden hat, ob die Probezeit bestanden sei. Der Verweis auf die genannten Bestimmungen wäre inhaltsleer, würde man davon ausgehen, dass die Remotion in der fünften Klasse ausgeschlossen ist. Alleine die § 3 (Promotionsfächer) und § 4 (Beförderung) rechtfertigten kaum einen Verweis, zumal es nicht am Platz wäre, diese Bestimmungen für "sinngemäss anwendbar" zu erklären. Im Kern kann der Verweis einzig das Regime der Remotionen betreffen. Dieses findet seine Grundlage in den §§ 5-7 LBVG/BS. Besteht damit nach § 9 Abs. 3 LBVG/BS auch in der Abschlussklasse eine Remotionsmöglichkeit, sind diesbezüglich die allgemeinen Regeln anwendbar, was bedeutet, dass die Zwei-Jahres-Frist im Sinne von § 18 Satz 1 LBVG/BS vorbehalten bleibt. Es ist damit jedenfalls nicht unhaltbar und hält einer Verfassungsprüfung stand, wenn die Vorinstanz zum Ergebnis gelangt, die Zwei-Jahres-Regel im Sinne von § 18 Satz 1 LBVG/BS müsse sich auf sämtliche Klassenwiederholungen beziehen.
5. 5.1 Die Beschwerdeführer rügen weiter die Verletzung des Gebotes von Treu und Glauben (<ref-law>). Sie nehmen insbesondere Anstoss daran, dass die von ihnen beantragte Verfügung erst am 29. Juni 2011 erging. Das widersprüchliche, zögerliche Verhalten der Behörden habe die Beschwerdeführer in der Annahme bestärken dürfen, einem Übertritt des Beschwerdeführers 2 in die fünfte Gymnasialklasse am Gymnasium B._ stehe wohl nichts entgegen. Auf das erweckte Vertrauen gestützt, habe der Beschwerdeführer insofern Dispositionen getroffen, als er berechtigterweise davon abgesehen habe, nach Alternativen zu suchen.
5.2 Den Beschwerdeführern musste bewusst sein, dass ihr Begehren um Zulassung des Beschwerdeführers 2 in die fünfte Gymnasialklasse am Gymnasium B._ wenig Aussichten auf Erfolg hatte. Nicht nur hatte sie die Rektorin des Gymnasiums A._ über die Rechtslage in Kenntnis gesetzt, was zum Ausschluss von der Schule führte und von den Beschwerdeführern nicht selbständig angefochten wurde, auch hatte sich der Rektor des Gymnasiums B._ in der selben Weise geäussert, sobald ihm die Sachumstände vollständig bekannt waren. Ein Rückschluss aus der Verfahrensdauer auf den Ausgang des Verfahrens drängte sich keineswegs auf. Der in <ref-law> verankerte Grundsatz von Treu und Glauben verleiht einer Person Anspruch auf Schutz eines objektiv berechtigten Vertrauens in behördliche Zusicherungen oder sonstiges, bestimmte Erwartungen begründendes Vertrauen der Behörden (<ref-ruling> E. 6.1 S. 636 f. mit Hinweisen). Äusserungen im Verkehr zwischen Behörden und Privaten sind dabei zu interpretieren, wie die jeweils andere Seite sie nach Treu und Glauben verstehen durfte (<ref-ruling> E. 4b S. 104 f.). Hinzu kommt, dass die blosse Untätigkeit einer Behörde, von welcher die Beschwerdeführer hier ausgehen und auf die sie sich berufen, in aller Regel keinen Vertrauenstatbestand zu schaffen vermag (<ref-ruling> E. 8.1 S. 45, mit Hinweisen). Ob die Behörde infolge Untätigkeit ausnahmsweise einen solchen geschaffen hat, bestimmt sich grundsätzlich danach, ob ihr Stillschweigen bei objektiver Betrachtungsweise geeignet war, beim Beschwerdeführer eine entsprechende Erwartung zu wecken (<ref-ruling> E. 2.2 S. 25 f.; zum Ganzen Urteil 2C_350/2011 vom 17. Oktober 2011 E. 2.4, in: StR 67/2012 S. 75). Dies ist nach dem Gesagten hier nicht der Fall. Weder die Leitungen der beiden Gymnasien noch das Erziehungsdepartement oder die Dienststelle "Weiterführende Schulen" haben je einen Beitrag geleistet, der den Schluss zugelassen hätte, dass die Gutheissung des Antrags bevorstehe. Alleine aus der Verfahrensdauer zu folgern, es werde gut kommen, ist subjektiv verständlich, objektiv aber nicht zu begründen und damit ungenügend, um einen Vertauenstatbestand zu setzen.
6. Unstreitig ist, dass der Antrag auf Zulassung des Beschwerdeführers 2 zur Repetition der fünften Gymnasialklasse während vier Monaten unbearbeitet blieb, ehe die Dienststelle "Weiterführende Schulen" ihre Verfügung innerhalb eines einzigen Tages erliess. Wenn die Beschwerdeführenden meinen, bei der kurzen Bearbeitungsdauer müsse in der "Art des Zustandekommens des Entscheides" geradezu Willkür liegen, so geht dies fehl. Die Dienststelle "Weiterführende Schulen" konnte sich bei ihren Überlegungen auf die Abklärungen und Äusserungen der Rektorin des Gymnasiums A._ sowie des Rektors des Gymnasiums B._ stützen. Weitere Abklärungen tatsächlicher Art, die allenfalls einen gewissen Zeitbedarf ausgelöst hätten, erübrigten sich. Angesichts der aus ihrer Optik klaren Rechtslage durfte die Dienststelle willkürfrei innerhalb eines Tages entscheiden.
7. Gemäss § 11 Abs. 1 lit. n der Verfassung des Kantons Basel-Stadt vom 23. März 2005 (KV/BS; SR 131.222.1) sind die Grundrechte im Rahmen der Bundesverfassung und der für die Schweiz verbindlichen internationalen Abkommen gewährleistet, so namentlich das Recht auf Bildung. Rügen die Beschwerdeführer eine Verletzung des Rechts auf Bildung, setzen sie voraus, dass kraft kantonalen Rechts ein justiziabler, im Einzelfall durchsetzbarer Individualanspruch auf Bildung bestehe. Dies bedingte seinerseits, dass das kantonale Recht über <ref-law> hinausginge, der lediglich einen Anspruch auf Grundschulunterricht verleiht. Der von Bundesverfassungs wegen garantierte Grundschulunterricht bezieht sich auf die Primar- und Sekundarstufe I, also auf die sog. "obligatorische Schulzeit". Nicht davon erfasst ist schon der Unterricht an (staatlichen) Untergymnasien (<ref-ruling> E. 3.5.3 S. 163; <ref-ruling> E. 7.4 S. 39), umso weniger jener an einer allgemeinbildenden Maturitätsschule (Gymnasium), welche auf dem Untergymnasium aufbaut (vgl. zur Maturitätsschule Art. 4 der Verordnung vom 15. Februar 1995 über die Anerkennung von gymnasialen Maturitätsausweisen [MAV; SR 413.11]). Davon auszugehen, dass das hier massgebende Recht des Kantons Basel-Stadt einen Anspruch auf Besuch der Sekundarstufe II vermittelt, besteht kein Anlass. So oder anders bestünde ein solcher Anspruch nicht voraussetzungslos, sondern nur, wenn die entsprechenden Voraussetzungen erfüllt sind, was hier nicht der Fall ist.
8. 8.1 Dem angefochtenen Entscheid ist mithin keine Rechtsverletzung zu entnehmen, sodass die Beschwerde als unbegründet abzuweisen ist. Entsprechend ist auch die Kostenregelung der Vorinstanz nicht zu beanstanden.
8.2 Mit dem Entscheid in der Sache ist das Gesuch um Anordnung der aufschiebenden Wirkung gegenstandslos.
8.3 Die unterliegenden Beschwerdeführer haben die Kosten des bundesgerichtlichen Verfahrens zu gleichen Teilen und unter solidarischer Haftung zu tragen (Art. 65 und 66 Abs. 1 und 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden zu gleichen Teilen und unter solidarischer Haftung den Beschwerdeführern auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht schriftlich mitgeteilt.
Lausanne, 11. Mai 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Kocher