Sachverhalt:
A. Der tunesische Staatsangehörige A._ ersuchte am 25. Oktober 2006 den Stadtschulrat der Stadt Schaffhausen, seine beiden Söhne X._ (geb. 1995) und Y._ (geb. 1997) vom obligatorischen Schwimmunterricht an der Primarschule Steingut (5. bzw. 4. Klasse) zu dispensieren. Er verwies darauf, dass seine Familie dem Islam angehöre und ein geschlechtlich gemischter Schwimmunterricht mit ihren religiösen Überzeugungen nicht vereinbar sei. Die zuständige Kreisschulbehörde des Stadtschulrats lehnte das Gesuch am 1. November 2006 ab. Der Erziehungsrat des Kantons Schaffhausen wies den Rekurs, den X._ und Y._ gegen diesen Entscheid erhoben hatten, am 11. April 2007 ebenfalls ab. Die beim Obergericht des Kantons Schaffhausen dagegen eingereichte Beschwerde blieb ohne Erfolg.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen X._ und Y._ dem Bundesgericht, den Entscheid des Obergerichts des Kantons Schaffhausen vom 14. Dezember 2007 aufzuheben und die Sache zu neuem Entscheid an dieses zurückzuweisen, eventuell sie vom gemeinsamen Schwimmunterricht mit den Mädchen zu dispensieren.
Der Stadtschulrat und der Erziehungsrat stellen gemeinsam den Antrag, die Beschwerde abzuweisen, soweit darauf einzutreten sei.
Das Obergericht hat sich zur Beschwerde vernehmen lassen, ohne einen ausdrücklichen Antrag zu stellen.
Das Bundesgericht hat die Beschwerde in öffentlicher Sitzung beurteilt.

Erwägungen:
1. 1.1 Das in Frage stehende Gesuch um Befreiung vom Schwimmunterricht wurde vor mehr als zwei Jahren gestellt. Ob die Beschwerdeführer heute noch ein aktuelles Rechtsschutzinteresse an der Aufhebung des angefochtenen Entscheides haben (<ref-law>), kann offen bleiben, da sich die mit der Beschwerde aufgeworfene Frage jederzeit und unter gleichen oder ähnlichen Umständen wieder stellen könnte, an ihrer Beantwortung wegen ihrer grundsätzlichen Bedeutung ein hinreichendes öffentliches Interesse besteht und eine rechtzeitige bundesgerichtliche Prüfung im Einzelfall kaum je möglich wäre (vgl. <ref-ruling> E. 1.2).
1.2 Die vorliegende Beschwerde ist von den beiden Beschwerdeführern (geb. 1995 und 1997), gesetzlich vertreten durch ihre Eltern, erhoben worden. Die beiden Knaben sind heute noch nicht 16 Jahre alt, womit gemäss <ref-law> noch die Eltern über ihre religiöse Erziehung verfügen. Vor Vollendung des 16. Altersjahres kann sich das urteilsfähige Kind (<ref-law>) zwar selber auf seine Glaubens- und Gewissensfreiheit berufen; wahrzunehmen sind seine Rechte jedoch grundsätzlich durch die Eltern (<ref-law>; <ref-ruling> E. 2b). Auf deren form- und fristgerechte Beschwerde ist daher einzutreten.
2. 2.1 Streitgegenstand bildet die Frage, ob die beiden Beschwerdeführer männlichen Geschlechts gestützt auf die Glaubens- und Gewissensfreiheit (<ref-law> und Art. 9 EMRK) Anspruch auf Dispensation vom Besuch des gemischtgeschlechtlichen Schwimmunterrichts an der Primarschule Schaffhausen haben.
2.2 Die kantonalen Instanzen haben dies verneint und änderten damit ihre eigene bisherige Praxis, nach welcher Knaben und Mädchen islamischen Glaubens eine solche Dispensation gewährt wurde. Die zuvor eingenommene Haltung der Behörden stützte sich auf einen Entscheid des Bundesgerichts aus dem Jahre 1993, in dem ein Recht muslimischer Schülerinnen auf Befreiung vom Schwimmunterricht grundsätzlich anerkannt worden war (<ref-ruling> ff.). Die inzwischen eingetretenen soziokulturellen Veränderungen haben bei den kantonalen Behörden in dieser Frage zu einem Meinungsumschwung geführt. Die Vorinstanz legt im angefochtenen Entscheid die Gründe, die eine Praxisänderung rechtfertigten, näher dar. So spreche eine Güterabwägung unter den heute gegebenen tatsächlichen und rechtlichen Verhältnissen gegen eine Dispensation muslimischer Schulkinder - Knaben und Mädchen - vom gemischtgeschlechtlichen Schwimmunterricht, da es einerseits nicht um eine zentrale, allgemein anerkannte Forderung muslimischen Glaubens gehe und anderseits erhebliche und überwiegende Interessen der Geschlechtergleichstellung und der gesellschaftlichen Integration der Ausländer eine Teilnahme aller Schüler an diesem Unterricht erforderten.
Die Beschwerdeführer bestreiten, dass triftige Gründe für die vorgenommene Praxisänderung vorliegen. Die Vorinstanz übersehe, dass die Religionsfreiheit alle Glaubenssätze - auch die weniger zentralen - schütze, eine erfolgreiche Integration Toleranz in Glaubensfragen voraussetze und sich die Verhältnisse seit dem letzten Entscheid des Bundesgerichts überhaupt nicht verändert hätten.
3. Eine Änderung der Praxis lässt sich regelmässig nur begründen, wenn die neue Lösung besserer Erkenntnis der ratio legis, veränderten äusseren Verhältnissen oder gewandelter Rechtsanschauung entspricht; andernfalls ist die bisherige Praxis beizubehalten (<ref-ruling> E. 4 S. 777). Eine Praxisänderung muss sich deshalb auf ernsthafte sachliche Gründe stützen können, die - vor allem im Interesse der Rechtssicherheit - umso gewichtiger sein müssen, je länger die als falsch oder nicht mehr zeitgemäss erachtete Rechtsanwendung gehandhabt worden ist (<ref-ruling> E. 5 S. 129). Es ist zu prüfen, ob die von der Vorinstanz angeführten Argumente so gewichtig sind, dass sich eine Änderung der vom Bundesgericht eingehend begründeten Rechtsprechung rechtfertigt.
4. 4.1 Knaben und Mädchen streng islamischen Glaubens ist es untersagt, an einem gemischtgeschlechtlichen Schwimmunterricht teilzunehmen. Das gilt aus religiös-erzieherischen Gründen bereits für die Zeit vor Eintritt der Geschlechtsreife. Eine Ausnahme besteht nur für im Koran näher umschriebene Angehörige (<ref-ruling> E. 4d S. 186).
4.2 Die Beschwerdeführer berufen sich auf diese Glaubensregel. Sie haben im kantonalen Verfahren eine am 5. Februar 2007 verfasste Erklärung des Imams der Grossen Moschee von Genf eingereicht, woraus hervorgeht, dass Schwimmen nicht erlaubt sei, wo Mädchen und Knaben zusammen seien; es gelte zu verhindern, dass sie gegenseitig ihre Reize betrachteten. Die Beschwerdeführer machen ausdrücklich geltend, nach den muslimischen Geboten dürften sie als Gläubige nicht den weitgehend nackten Körper des anderen Geschlechts sehen; beim Schwimmen träfen sie auf Mädchen, die viel weniger bekleidet seien, als dies der Glaube erlaube; der Koran auferlege dem Gläubigen, den Blick zu senken, wenn ihm Menschen begegneten, deren Awra (Körper zwischen Bauchnabel und Knie) nicht bedeckt sei; dieses Gebot könnten die Beschwerdeführer beim gemeinsamen Schwimmen mit den Mädchen nicht einhalten (Beschwerde S. 7 f.). Da die Beschwerdeführer insoweit keine Einschränkung anbringen, ist davon auszugehen, dass dieses Gebot für sie unabhängig von der Glaubenszugehörigkeit der Mädchen gilt.
4.3 Die Vorinstanz anerkennt, dass die Beachtung der erwähnten religiösen Vorschrift verfassungsrechtlichen Schutz geniesst. Sie führt jedoch aus, dass nur ein Teil der muslimischen Bevölkerung den Koran in diesem strengen Sinn interpretiere. Für die anderen genüge es, dass der Körper hinreichend bedeckt und die Intimsphäre geschützt sei. Das Verbot des gemischtgeschlechtlichen Schwimmens zähle deshalb nicht zu den zentralen Forderungen des muslimischen Glaubens, sondern sei Ausfluss einer sehr strengen dogmatischen bzw. patriarchalischen Auffassung, die von vielen Muslimen nicht geteilt werde. Dafür könne zwar der Schutz der Religionsfreiheit beansprucht werden, doch komme ihm bei der Interessenabwägung ein geringeres Gewicht zu als anderen Glaubensinhalten.
4.4 Der religiös neutrale Staat kann Glaubensregeln nicht auf ihre theologische Richtigkeit - insbesondere nicht auf ihre Übereinstimmung mit den heiligen Schriften - überprüfen (vgl. <ref-ruling> E. 4c S. 185). Ebenso ist es ihm verwehrt, die Bedeutung einer religiösen Vorschrift und damit ihr Gewicht bei der Interessenabwägung selber festzustellen. In diesem Punkt haben die staatlichen Organe vielmehr von der Bedeutung auszugehen, welche die religiöse Norm für die Beschwerdeführer hat. In einem neuen Entscheid hat das Bundesgericht in Bestätigung dieser Rechtsprechung erklärt, Glaubensinhalte, die ein religiös motiviertes Verhalten begründen oder bestimmte Bekleidungsweisen nahelegen, seien grundsätzlich nicht zu überprüfen (<ref-ruling> E. 4 und 5.2).
Das verkennt die Vorinstanz, wenn sie dem Verbot des gleichgeschlechtlichen Schwimmens deshalb einen geringen Stellenwert einräumt, weil es für die Mehrheit der Muslime nicht zu den zentralen Forderungen ihres Glaubens gehöre. Die Beschwerdeführer teilen in dieser Hinsicht gerade nicht die religiösen Auffassungen der Mehrheit der hier lebenden Muslime. Sie machen vielmehr geltend, es stehe für sie ein absolutes Verbot in Frage, über das sie sich nicht hinwegsetzen könnten. Im kantonalen Verfahren ist die Glaubwürdigkeit dieser Behauptung nicht in Zweifel gezogen worden. Wie das Bundesgericht bereits früher festgestellt hat, hängt eine erfolgreiche Berufung auf die Religionsfreiheit nicht davon ab, ob eine religiöse Überzeugung stark vom Landesüblichen abweicht oder ob sie von allen Glaubensangehörigen gleichermassen befolgt wird. Dieses Grundrecht schützt vielmehr ebenso die Überzeugungen religiöser Minderheiten (<ref-ruling> E. 7e S. 193 und E. 8a S. 194).
4.5 Indem die Vorinstanz der von den Beschwerdeführern angerufenen religiösen Glaubensregel nur einen beschränkten Stellenwert einräumt, weicht sie von der bisherigen und erst kürzlich bestätigten Rechtsprechung in einem zentralen Punkt ab. Ihre dafür angeführte Begründung vermag nicht zu überzeugen, so dass insoweit kein Anlass für eine Praxisänderung besteht.
4.6 Es ist demnach davon auszugehen, dass die Verpflichtung zur Teilnahme am gemischtgeschlechtlichen Schwimmunterricht einen Eingriff in die Religionsfreiheit der Beschwerdeführer darstellt.
5. 5.1 Die durch <ref-law> und Art. 9 EMRK sowie den von den Beschwerdeführern nicht angerufenen Art. 18 UNO-Pakt II (SR 0.103.2) gleichermassen gewährleistete Religionsfreiheit umfasst sowohl die innere Freiheit, zu glauben, nicht zu glauben oder seine religiösen Anschauungen zu ändern, wie auch die äussere Freiheit, entsprechende Überzeugungen - innerhalb gewisser Schranken - zu äussern, zu praktizieren und zu verbreiten. Zum nicht einschränkbaren Kernbereich gehört einzig die innere Religionsfreiheit im Sinne der inneren Überzeugung; die äussere Glaubensfreiheit kann hingegen unter den Voraussetzungen von <ref-law> eingeschränkt werden (vgl. <ref-ruling> E. 4.3, mit Hinweisen).
5.2 Dass die in Frage stehende Verpflichtung nicht den unantastbaren Kerngehalt der Religionsfreiheit berührt, liegt auf der Hand. Betroffen sind Konflikte, die daraus entstehen können, dass gewisse kulturell-religiös verankerte, inhaltlich jedoch das Alltagsleben betreffende Verhaltensnormen mit der in der Schweiz geltenden staatlichen Rechtsordnung kollidieren. Es ist somit zu prüfen, ob die Verpflichtung eine unter dem Blickwinkel von <ref-law> zulässige Einschränkung der Glaubens- und Gewissensfreiheit der Beschwerdeführer darstellt.
6. 6.1 Die Beschwerdeführer rügen erstmals vor Bundesgericht das Fehlen einer hinreichenden gesetzlichen Grundlage.
6.2 Personengruppen, die wie Primarschüler zum Staat in einer besonders engen Rechtsbeziehung stehen (sogenanntes Sonderstatus- oder besonderes Rechtsverhältnis), können sich grundsätzlich ebenfalls auf die Religionsfreiheit berufen. In solchen Fällen hat die formellgesetzliche Regelung - abgesehen von der Begründung des Sonderstatusverhältnisses selber - allerdings nicht ins Detail zu gehen, sondern darf der Natur des Rechtsverhältnisses entsprechend weit gefasst sein; namentlich darf die Regelung der Einzelheiten an Exekutivorgane delegiert werden (vgl. <ref-ruling> E. 3, mit Hinweisen).
6.3 Der Turn- und Sportunterricht ist an allen Volksschulen obligatorisch (<ref-law>, Art. 2 Abs. 2 des Bundesgesetzes vom 17. März 1972 über die Förderung von Turnen und Sport [SR 415.0]). Die damit erfassten Sportfächer werden vom Bundesrecht nicht näher umschrieben. Sie werden indessen im Kanton Schaffhausen durch den Lehrplan bestimmt, der vom Erziehungsrat erlassen wird. Die (mehrere hundert Seiten umfassenden) Lehrpläne werden seit 1985 nicht mehr im Amtsblatt veröffentlicht und in die kantonale Gesetzessammlung und das Rechtsbuch aufgenommen; sie können jedoch beim kantonalen Erziehungssekretariat eingesehen werden (Art. 22 Abs. 1 des kantonalen Schulgesetzes vom 27. April 1981 [SchulG/SH], Fn 14). Der Lehrplan ist auch im Internet auf der Serviceplattform Bildung des Kantons Schaffhausen ohne weiteres zu finden (Suchbegriff: "Lehrplan Schaffhausen"). Entgegen der Behauptung der Beschwerdeführer ist somit kein besonderes Computerprogramm erforderlich, welches nur gegen eine Entschädigung erworben werden kann.
Nach dem Lehrplan des Kantons Schaffhausen zählt zum Fachbereich Sport (Unterstufe) der Lernbereich Spiel und Sport im Wasser; eines der Lernziele bildet das Beherrschen einer frei wählbaren Schwimmart. Schwimmen ist somit im Kanton Schaffhausen Teil des obligatorischen Sportunterrichts.
6.4 Gemäss <ref-law> sorgen die Kantone für einen ausreichenden Grundschulunterricht, der obligatorisch ist und allen Kindern offen steht. Diese Bestimmung trifft keine Unterscheidungen nach der Geschlechtszugehörigkeit der Kinder; es ist daher davon auszugehen, dass von Verfassungs wegen der Grundschulunterricht grundsätzlich gemischtgeschlechtlich erteilt werden kann.
Das kantonale Schulgesetz hält in dieser Hinsicht fest, dass beide Geschlechter Anspruch auf gleiche Bildungsmöglichkeiten haben (Art. 19 Abs. 1 SchulG/SH) und dass für Knaben und Mädchen die gleiche Ausbildung anzubieten ist (Art. 22 Abs. 3 SchulG/SH). Da somit auf Stufe der Grundschule keine Trennung der Geschlechter vorgesehen ist, darf bzw. soll auch der obligatorische Schwimmunterricht nach der gesetzlichen Regelung des Kantons Schaffhausen grundsätzlich gemischtgeschlechtlich stattfinden. Dass der Sportunterricht in höheren Klassen bzw. an der Oberstufe im Kanton Schaffhausen nach Geschlechtern getrennt erteilt wird, steht dem nicht entgegen.
6.5 Angesichts des Sonderstatusverhältnisses, dem die Grundschüler unterstehen, bildet die in Frage stehende kantonale Regelung eine genügende gesetzliche Grundlage für den obligatorischen, gemischtgeschlechtlichen Schwimmunterricht an der Unterstufe der öffentlichen Grundschulen im Kanton Schaffhausen. Die nähere normative Regelung braucht nicht in einem Gesetz im formellen Sinn festgelegt zu sein (vgl. <ref-ruling> E. 6c).
7. 7.1 Das Obligatorium des Schulbesuches - einschliesslich der vom kantonalen Recht statuierten Pflicht zur Teilnahme am Schwimmen im Rahmen des Sportunterrichts - dient der Wahrung der Chancengleichheit aller Kinder und darüber hinaus auch derjenigen zwischen den Geschlechtern bzw. der Gleichstellung von Mann und Frau in der (Aus-)Bildung; sie fördert zudem die Integration von Angehörigen anderer Länder, Kulturen und Religionen und ist somit unbestrittenermassen von gewichtigem öffentlichen Interesse (<ref-ruling> E. 7c). Dies wird von den Beschwerdeführern zu Recht nicht in Frage gestellt. Soweit im zitierten Urteil das Schwimmen als verzichtbarer Lehrinhalt bezeichnet wird, kann daran - nachdem inzwischen am 24. Februar 1997 die UNO-Kinderrechtskonvention in Kraft getreten ist, welche insbesondere festschreibt, dass bei allen Massnahmen, die Kinder betreffen, das Wohl des Kindes vorrangig zu berücksichtigen ist (Art. 3 Ziff. 1) - nicht festgehalten werden. Denn heute werden immer mehr Wassersportarten auch von Kindern und Jugendlichen ausgeübt (Aquaparks, Thermalbäder, Kanufahren, Riverrafting, Wasserwandern, Windsurfen etc.). Es ist deshalb zunehmend von Bedeutung, dass schon Kinder mit dem Element Wasser vertraut gemacht werden und schwimmen können. Mitunter ertrinken heute Kinder und Jugendliche - u.a. auch bei Schulanlässen -, weil sie nicht schwimmen können (vgl. Urteil 6S.358/2004 vom 10. November 2004: Tod eines Schülers, der beim Besuch eines Aquaparks verschwieg, dass er Nichtschwimmer war). Dem gemeinsam geführten Sportunterricht kommt im in der Schweiz bestehenden gesellschaftlichen Umfeld zudem eine - im Interesse des Kindes liegende - wichtige sozialisierende Funktion zu. Insbesondere gilt es zu vermeiden, dass die Kinder islamischen Glaubens bereits auf der Schulstufe in eine Aussenseiterrolle gedrängt werden.
Es besteht somit ein erhebliches öffentliches Interesse am Besuch des Schwimmunterrichts durch alle Schüler, die den sich dabei stellenden Anforderungen körperlich auch gewachsen sind.
7.2 Das öffentliche Interesse, dass alle Schüler den obligatorischen gemischtgeschlechtlichen Schwimmunterricht besuchen, ist abzuwägen gegenüber dem Interesse der Beschwerdeführer, sich auf die Einhaltung einer nach ihrer Auffassung wesentlichen religiösen Regel berufen zu können. Dabei ist von Bedeutung, dass nicht etwa die Teilnahme an einer Veranstaltung in Frage steht, die inhaltlich einen Bezug zu religiösen Überzeugungen hätte, wie dies bei der Erteilung von Religionsunterricht oder bei eigentlichen Kulthandlungen der Fall wäre. Es geht nicht um den Inhalt des Lehrstoffes - auch Muslime halten Sport- und Schwimmunterricht für sinnvoll -, sondern allein um die äusseren Bedingungen der Unterrichtserteilung.
Seit dem Entscheid des Bundesgerichts im Jahre 1993 haben die bereits in jenem Entscheid berücksichtigten wichtigen Integrationsanliegen in der Öffentlichkeit noch vermehrtes Gewicht erhalten. Ihre ausdrückliche Aufnahme im Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Art. 4 und 53 ff. AuG; SR 142.20; vgl. auch Art. 85 Abs. 2 KV/SH) belegt diese Entwicklung. Verändert hat sich auch die religiöse Zusammensetzung der schweizerischen Wohnbevölkerung: Während im Jahre 1990 noch 152'200 Angehörige islamischer Gemeinschaften in der Schweiz lebten, waren es im Jahr 2000 bereits 310'800 (davon 88,3% Ausländer [56,4% aus Ex-Jugoslawien, v.a. aus dem Kosovo; 20,2% aus der Türkei], 3,9% Schweizer seit der Geburt: vgl. CLAUDE BOVAY, Eidgenössische Volkszählung 2000, Religionslandschaft in der Schweiz, Bundesamt für Statistik, Neuenburg, Dezember 2004). Heute wird ihre Zahl auf gegen 400'000 geschätzt (UWE STOLZ, Schweiz auf dem Weg zum Islam-Staat, Internet: www.israswiss.ch). Die islamische Wohnbevölkerung liegt jedenfalls bereits seit 1980 zahlenmässig nach der römisch-katholischen und der evangelisch-reformierten an dritter Stelle. Diese Zahlen zeigen, dass Streitigkeiten über einen Dispens vom Schwimmunterricht zwar auch Muslime schweizerischer Nationalität treffen können; sie präsentieren sich indessen schwergewichtig als Problem der Ausländerintegration. Die Vorinstanz spricht daher denn auch zu Recht von einer "multikulturellen Schulrealität". Diese verlangt heute noch vermehrt als früher Anstrengungen zur Angewöhnung und Einbindung der Kinder und Jugendlichen aus anderen Kulturen in die hier geltenden gesellschaftlichen Rahmenbedingungen. Nur auf diese Weise kann ihre Teilnahme am wirtschaftlichen, sozialen und kulturellen Leben und damit der soziale Frieden und die Chancengleichheit gewährleistet werden. Aufgabe des Verfassungsstaates ist namentlich, ein Mindestmass an innerem Zusammenhalt von Staat und Gesamtgesellschaft herzustellen, welches für ein harmonisches, von Achtung und Toleranz geprägtes Zusammenleben notwendig ist (vgl. Probleme der Integration von Ausländerinnen und Ausländern in der Schweiz, Bundesamt für Migration, Juli 2006, S. 86).
Von Ausländern darf und muss erwartet werden, dass sie zum Zusammenleben mit der einheimischen Bevölkerung bereit sind und die schweizerische Rechtsordnung mit ihren demokratischen und rechtsstaatlichen Grundsätzen - die der Staat auch gegenüber kulturell begründeten abweichenden Ansprüchen zu bewahren hat - sowie die hiesigen sozialen und gesellschaftlichen Gegebenheiten akzeptieren (vgl. Botschaft des Bundesrates vom 8. März 2002 zum Bundesgesetz über die Ausländerinnen und Ausländer, BBl 2002 3714, 3797 ff.). Wer in ein anderes Land emigriert, muss regelmässig gewisse Einschränkungen und Änderungen seiner Lebensgewohnheiten in Kauf nehmen. Dies bedeutet keineswegs eine Preisgabe der Religionsfreiheit. Es geht dabei regelmässig nicht um den Kerngehalt dieses Grundrechts, sondern lediglich um Konflikte, die daraus entstehen können, dass gewisse kulturell-religiös verankerte, inhaltlich aber das Alltagsleben betreffende Verhaltensnormen mit den hier geltenden Regeln kollidieren. Glaubensansichten entbinden jedoch nicht von der Erfüllung der bürgerlichen Pflichten. Diese in der bisherigen Bundesverfassung (Art. 49 Abs. 5 aBV) noch ausdrücklich verankerte Regel muss als Grundsatz weiterhin gelten.
Im sozialen Einbindungsprozess kommt der Schule eine besonders wichtige Aufgabe zu (vgl. BBl 2002 3800 f.). Sie soll zunächst eine Grundbildung vermitteln. Dieses Ziel kann sie nur erreichen, wenn seitens der Schüler die Verpflichtung besteht, die obligatorischen Fächer und Veranstaltungen zu besuchen. Im Gegenzug muss die Schule ein offenes, gesellschaftsübliches Umfeld bieten und den Geboten der weltanschaulichen Neutralität und der Laizität strikt nachleben. In diesem Rahmen darf die Schule angesichts der grossen Bedeutung des Pflichtangebots aber darauf bestehen, dass ihre Lehrveranstaltungen für alle obligatorisch sind und dass sie nicht für alle persönlichen Wünsche eine abweichende Sonderregelung vorsehen oder zulassen muss. Dies gilt auch für Ausnahmen zur Beachtung religiöser Gebote, die mit dem Schulprogramm kollidieren. Dem obligatorischen Schulunterricht kommt hier grundsätzlich der Vorrang zu, weshalb allfällige Ausnahmen nur mit Zurückhaltung zu gewähren sind. Der Sportunterricht dient zudem in hohem Mass der Sozialisierung der Schüler. Diesen Zweck kann er nur erfüllen, wenn der Unterricht (wie auch Klassenlager und Skilager etc.), wie in der Schweiz allgemein üblich, gemeinsam stattfindet.
Bei der Interessenabwägung ist zu berücksichtigen, dass es beim hier in Frage stehenden Verbot darum geht, dass die beiden männlichen Beschwerdeführer beim Besuch des obligatorischen gemischtgeschlechtlichen Schwimmunterrichts gezwungen wären, bestimmte Teile des weiblichen Köpers im Bereich vom Bauchnabel bis zu den Knien zu sehen. Es liegt auf der Hand, dass sich solche Anblicke für die Beschwerdeführer beim gemeinsamen Schwimmunterricht mit Mitschülerinnen in Badekostümen nicht vermeiden lassen. Dies gilt indessen in der Schweiz für viele Bereiche des alltäglichen Lebens. Denn es lässt sich nicht verhindern, dass die Beschwerdeführer hier täglich Frauen und Mädchen erblicken, bei welchen der in Frage stehende Körperbereich teilweise unverhüllt sichtbar ist. Bauchfreie Bekleidung und kurze Röcke gehören (auch) in der Schweiz zum üblichen Strassenbild. Im Alltag kann den Beschwerdeführern die Konfrontation mit in der Schweiz gängigen Bekleidungsformen somit ohnehin nicht erspart werden. Dies gilt auch in den übrigen europäischen Staaten. In all diesen Ländern werden Kinder nicht nur durch Begegnungen auf der Strasse, sondern auch durch Abbildungen in den Medien mit knapp bekleideten menschlichen Körpern des anderen Geschlechts konfrontiert und müssen damit umzugehen lernen.
Es kommt weiter hinzu, dass die hier in Frage stehende Glaubensregel auch nicht mit den für die Mädchen islamischen Glaubens geltenden Bekleidungsvorschriften gleichgestellt werden kann. Diese gebieten den Frauen das Verhüllen des eigenen Körpers und richten sich an die Gläubigen selber. Die Frauen können selber entscheiden, ob sie diese Gebote befolgen wollen. Anders verhält es sich beim verpönten Anblick von Körperteilen des anderen Geschlechts. Hier kann der gläubige Schüler nicht verlangen, dass die Mitschülerinnen anderen Glaubens ihren Körper entsprechend den islamischen Bekleidungsvorschriften verhüllen, nur um ihm diesen Anblick zu ersparen.
Die Anerkennung eines Rechts, muslimische Kinder generell vom kollektiven Schwimmunterricht zu befreien, würde den vielfältigen Bestrebungen zur Integration dieser Bevölkerungsgruppe zuwiderlaufen. Namentlich würde damit den betroffenen Kindern erheblich erschwert, sich an das in der hiesigen Gesellschaft übliche natürliche Zusammensein mit dem anderen Geschlecht zu gewöhnen. Die Kinder müssten zur Vermeidung des Anblicks von Personen des anderen Geschlechts in Badekostümen sogar auf die Benützung öffentlicher Badeanstalten und Strandbäder verzichten.
7.3 Wenn daher die Behörden des Kantons Schaffhausen gestützt auf die im angefochtenen Entscheid angestellten grundsätzlichen Erwägungen die bisherige Dispensationspraxis nicht weiterführen, sondern den gemischtgeschlechtlichen Schwimmunterricht - verbunden mit flankierenden Massnahmen (eigene körperbedeckende Badebekleidung, getrenntes Umziehen und Duschen) - auch für moslemische Kinder vorschreiben wollen, kann darin kein unzulässiger Eingriff in die Religionsfreiheit erblickt werden.
Der vorliegende Fall ist im Übrigen nicht vergleichbar mit dem in <ref-ruling> beurteilten Sachverhalt. Dort ging es nicht um regelmässig stattfindenden obligatorischen Unterricht, sondern um die einmal abzulegende Maturitätsprüfung: Streitig war die Verweigerung eines Dispenses gegenüber einem Schüler, welcher einer dem Gebot der Samstags-Ruhe strikt verpflichteten Glaubensgemeinschaft angehört, von schriftlichen Maturitätsprüfungen an einem Samstag. Diese Grundrechtseinschränkung erachtete das Bundesgericht als unverhältnismässig, da insbesondere wegen krankheits- und unfallbedingten Absenzen ohnehin Nachholtermine an anderen Tagen vorgesehen werden mussten und nichts entgegen stand, den Schüler an solchen Terminen zur Prüfung aufzubieten.
8. Die Beschwerde ist aus diesen Gründen abzuweisen. Da die Rechtsbegehren der Beschwerdeführer nicht aussichtslos erschienen und die weiteren Voraussetzungen (<ref-law>) erfüllt sind, ist ihnen die unentgeltliche Rechtspflege und Verbeiständung zu gewähren. Auf die Erhebung von Gerichtskosten wird verzichtet.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Den Beschwerdeführern wird für das Verfahren vor Bundesgericht die unentgeltliche Rechtspflege gewährt.
a) Es werden keine Gerichtskosten erhoben.
b) Rechtsanwalt Gerold Meier, Schaffhausen, wird zum unentgeltlichen Rechtsbeistand bestellt und aus der Bundesgerichtskasse mit Fr. 3'000.-- entschädigt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 24. Oktober 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Küng