Sachverhalt:
A. X._ ist Sanitärinstallateur mit eidgenössischem Fähigkeitsausweis und betreibt ein Sanitärgeschäft in A._. Am 17. Oktober 1989 erteilte ihm der Gemeinderat A._ die Konzession für die Ausführung von Wasserleitungen und -installationen auf dem Gebiet der Gemeinde A._. Am 8. August 2007 ersuchte X._ die Städtischen Werke Schaffhausen und Neuhausen am Rheinfall (im Folgenden: Städtische Werke) um Erteilung einer Installationsbewilligung für die Ausführung von Gas- und Wasserinstallationen im Versorgungsgebiet der Gas- und Wasserwerke Schaffhausen und Neuhausen am Rheinfall. Die Städtischen Werke erteilten ihm am 21. September 2007 die Bewilligung für das Ausführen von Gasinstallationen, verweigerten ihm aber mit Verfügung vom 12. Juni 2008 die Berechtigung für Installationen an Haustechnikanlagen für Trinkwasser und Arbeiten an Wasserinstallationen, da er die erforderliche Fachkunde nicht nachgewiesen habe.
X._ erhob dagegen Einsprache an den Stadtrat der Stadt Schaffhausen und beantragte unter Hinweis auf Art. 2 des Bundesgesetzes vom 6. Oktober 1995 über den Binnenmarkt (Binnenmarktgesetz, BGBM; SR 943.02) die Bewilligung für Installationsarbeiten. Der Stadtrat wies die Einsprache am 23. Dezember 2008 ab.
B. X._ erhob dagegen Rekurs an den Regierungsrat des Kantons Schaffhausen. Mit Beschluss vom 17. November 2009 hiess der Regierungsrat den Rekurs gut, hob den Beschluss des Stadtrats sowie die Verfügung der Städtischen Werke auf und wies die Sache im Sinne der Erwägungen zur erneuten Prüfung des Gesuchs an die Städtischen Werke zurück. In den Erwägungen führte er aus, der Rekurrent habe nach Art. 2 Abs. 1, 3 und 5 BGBM grundsätzlich Anspruch, auf dem Versorgungsgebiet der Städtischen Werke tätig zu sein. Er habe eine Bewilligung der Gemeinde A._, die zwar im Unterschied zu den Städtischen Werken keine spezifischen fachlichen Voraussetzungen verlange und somit nicht gleichwertig sei. Das Installations-Reglement der Stadt Schaffhausen verlange einen Nachweis der Fachkundigkeit gemäss dem Regelwerk des Schweizerischen Vereins des Gas- und Wasserfaches (SVGW). Nach der massgebenden Richtlinie GW1 Ziff. 2.2.4 dürften Installationsarbeiten an Haustechnikanlagen von Personen ausgeführt werden, welche über das eidgenössische Fähigkeitszeugnis als Sanitärmonteur verfügten. Der Rekurrent verfüge über dieses Diplom und eine über 20-jährige tadellose Berufspraxis und habe 1993 einen Ausbildungskurs des SVGW erfolgreich absolviert. Er sei daher als ausreichend fachkundig zu betrachten. Weitere Anforderungen wären unverhältnismässig. Eine Verweigerung der Bewilligung käme nur in Frage, wenn die Bewilligungsbehörde nachweisen könnte, dass die Installationsarbeiten des Rekurrenten im Versorgungsgebiet A._ erhebliche Mängel aufweisen würden.
C. Dagegen erhob die Einwohnergemeinde Schaffhausen Beschwerde an das Obergericht des Kantons Schaffhausen mit dem Antrag, der Rekursentscheid sei aufzuheben und der Beschluss des Stadtrates vom 23. Dezember 2008 zu bestätigen. Das Obergericht hiess mit Entscheid von 26. November 2010 die Beschwerde teilweise gut, hob den Rekursentscheid des Regierungsrates auf und wies die Sache an die Städtischen Werke zurück, damit diese im Sinne der Erwägungen verfahren und neu entscheiden. Das Obergericht führte aus, entgegen der Auffassung des Regierungsrates gelte Ziff. 2.2.4 der Richtlinie GW1 nur für die ausführenden Installateure; die Betriebe, welche in eigener Verantwortung Installationsarbeiten ausführen, müssten aber gemäss Ziff. 2.2.1 für den vorgesehenen Tätigkeitsbereich fachkundig sein; der Nachweis der Fachkundigkeit müsse gemäss Ziff. 2.2.2 mit einem gültigen SVGW-Zertifikat nachgewiesen werden. Der Regierungsrat hätte die Fachkunde gestützt auf die Ziff. 2.2.1 und 2.2.2 prüfen müssen; X._ verfüge zwar offenbar über kein SVGW-Zertifikat, doch könne er unter bestimmten Voraussetzungen übergangsrechtlich ohne Nachweispflicht zertifiziert werden. Zu prüfen sei, ob er diese Voraussetzungen erfülle. In diesem Rahmen sei sodann auch zu prüfen, ob eine allfällige Marktzugangsbeschränkung aufgrund der städtischen Regelung mit <ref-law> vereinbar wäre.
D. Mit Eingabe vom 14. Januar 2011 erhebt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, der angefochtene Entscheid sei aufzuheben und es sei ihm die Berechtigung für Wasserinstallationen auf dem Versorgungsgebiet der Städtischen Werke zu erteilen. Eventualiter sei die Sache an die Vorinstanz zurückzuweisen und diese aufzufordern, dem Beschwerdeführer die Berechtigung zu erteilen.
Das Obergericht des Kantons Schaffhausen verzichtet auf eine Vernehmlassung. Der Regierungsrat des Kantons Schaffhausen beantragt Gutheissung und die Stadt Schaffhausen Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1. 1.1 Die fristgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten ist gegen den kantonal letztinstanzlichen Entscheid des Obergerichts grundsätzlich zulässig (vgl. Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2, Art. 100 BGG). Es ist kein Ausschlussgrund nach <ref-law> gegeben. Auch wenn es darum geht, ob der Beschwerdeführer fachliche Anforderungen für die Ausübung bestimmter Tätigkeiten erfüllt, greift Art. 83 lit. t BGG nicht, da nicht Fähigkeitsbewertungen als solche, sondern die Zulassung zur Tätigkeit zur Debatte stehen (Urteil 2C_57/2010 vom 4. Dezember 2010 E. 1 mit Hinweisen).
1.2 Der angefochtene Entscheid ist ein Rückweisungsentscheid und damit ein Zwischenentscheid (<ref-ruling> E. 4.2 S. 482). Zwischenentscheide im Sinne von <ref-law> können selbstständig angefochten werden, wenn sie einen nicht wieder gutzumachenden Nachteil bewirken (lit. a) oder wenn die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (lit. b). Näher zu prüfen sind hier die in <ref-law> genannten Eintretensvoraussetzungen.
1.2.1 Nach dieser Bestimmung ist die Beschwerde gegen einen Zwischenentscheid zulässig, wenn dieser einen Nachteil bewirken könnte, der auch durch einen für den Beschwerdeführer günstigen Endentscheid (sei es im kantonalen Verfahren oder in einem anschliessenden Verfahren vor Bundesgericht) nicht mehr behoben werden könnte. Die blosse Verzögerung oder Verteuerung des Verfahrens genügt generell nicht, um einen sofortigen Entscheid des Bundesgerichts zu erwirken. Immerhin muss sichergestellt werden, dass das Verfahren insgesamt dem verfassungsrechtlichen Gebot genügt, im Rahmen eines fairen Verfahrens innert angemessener Frist einen wirksamen Rechtsschutz zu gewähren (<ref-law>; Art. 6 Ziff. 1 EMRK). Unter diesem Aspekt kann es ausnahmsweise verfassungsrechtlich geboten sein, bereits auf eine Beschwerde gegen einen Zwischenentscheid einzutreten, wenn es rechtsstaatlich unzumutbar wäre, die Parteien auf die Anfechtung des Endentscheids zu verweisen (<ref-ruling> E. 1.2.1 S. 171 mit Hinweisen).
1.2.2 Im vorliegenden Fall ist zu berücksichtigen, dass der Beschwerdeführer bereits im August 2007 um Erteilung einer Bewilligung für die Ausführung von Wasserinstallationen ersuchte und möglicherweise noch geraume Zeit bis zum Vorliegen eines vor Bundesgericht anfechtbaren Endentscheids vergehen wird. <ref-law> verlangt in Bezug auf Beschränkungen des freien Zugangs zum Markt ausdrücklich ein einfaches und rasches Verfahren. Es erscheint damit unzumutbar, den Beschwerdeführer auf eine Anfechtung des Endentscheids zu verweisen, mit der Folge, dass das Verfahren bei Gutheissung der Beschwerde nochmals neu aufgerollt werden müsste und ihm während der Dauer des Verfahrens die Ausführung der in Frage stehenden Installationen verwehrt bliebe. Unter diesen Umständen erscheint es geboten, im vorliegenden Verfahren die selbstständige direkte Anfechtung des umstrittenen Zwischenentscheids zuzulassen (vgl. <ref-ruling> E. 1.2.2 S. 171).
2. 2.1 Die Ausgangslage des vorliegenden Verfahrens war in folgender Hinsicht von Anfang an klar: Der Beschwerdeführer beantragte die streitige Bewilligung gestützt auf das BGBM und seine langjährige Tätigkeit in A._. Die Städtischen Instanzen vertraten die Meinung, der Beschwerdeführer erfülle die vom kommunalen Recht verlangten Anforderungen an die Fachkunde nicht, gaben ihm aber Gelegenheit, den Nachweis der Fachkundigkeit anhand einer Überprüfung der von ihm ausgeführten Installationen durch eine fachkundige Installationskontrolle zu erbringen (Schreiben vom 15. April 2008). Der Beschwerdeführer erbrachte diesen Nachweis nicht, sondern ging davon aus, er habe gestützt auf das BGBM auch ohne einen solchen Nachweis Anspruch auf die Bewilligung.
2.2 Der Regierungsrat erwog, der hinreichende Schutz des Publikums könne grundsätzlich mit dem eidgenössischen Fähigkeitsausweis gewährleistet werden; weitergehende Erfordernisse wären eine unverhältnismässige Beschränkung der Wirtschaftsfreiheit. Das kommunale Installationsreglement enthalte keine Grundlage, um zusätzliche Installationsbelege zu verlangen. Weiter stünde die von der Gemeinde verlangte Überprüfung sämtlicher Installationen des Beschwerdeführers durch eine fachkundige Installationskontrolle im Widerspruch zum BGBM. Die Verweigerung einer Bewilligung käme nur in Frage, wenn die Bewilligungsbehörde nachweisen könne, dass seine Installationsarbeiten in A._ erhebliche Mängel aufwiesen. Der Regierungsrat hat somit nicht verkannt, dass der Beschwerdeführer die von der Gemeinde verlangten Anforderungen nicht erfüllt, sondern hat seinen Entscheid darauf abgestützt, dass diese kommunalen Anforderungen mit dem BGBM und der Wirtschaftsfreiheit nicht vereinbar seien.
2.3 Die Stadt begründete ihre Beschwerde an das Obergericht damit, der Regierungsrat habe das kommunale Recht falsch ausgelegt. Zudem stünden die Anforderungen, welche sie stelle, auch nicht im Widerspruch zum BGBM oder zur Wirtschaftsfreiheit. Sodann habe der Beschwerdeführer im Jahr 2007/2008 bei einer Wasserinstallation in Schaffhausen kein Rückschlagventil vor der Enthärterpatrone installiert, was einen gesundheitsgefährdenden Mangel darstelle. Der Beschwerdeführer nahm in seiner Beschwerdeantwort einerseits zur Auslegung des kommunalen Rechts Stellung, begründete andererseits aber seinen Anspruch auf die Installationsbewilligung auch mit dem BGBM. Er bestritt sodann duplikweise eingehend den Vorwurf der mangelhaften Installation.
2.4 Streitthema vor Obergericht war somit einerseits die Frage der Auslegung des kommunalen Rechts, andererseits die Frage, ob das gemäss Auffassung der Stadt ausgelegte kommunale Recht mit dem BGBM vereinbar sei. Das Obergericht hat sich nur zur Auslegung des kommunalen Rechts geäussert mit dem Ergebnis, dass der Beschwerdeführer nach dieser Regelung keinen Anspruch auf Bewilligung habe. Sodann hat es die Städtischen Werke angewiesen zu prüfen, ob der heutige Beschwerdeführer die Fachkunde auch ohne Zertifikat bewiesen habe und ob eine allfällige Marktzugangsbeschränkung aufgrund der städtischen Regelung mit dem BGBM vereinbar wäre. Das Obergericht hat also die Städtischen Werke beauftragt, genau diejenigen Fragen nochmals zu prüfen, welche sowohl die städtischen Instanzen als auch der Regierungsrat bereits geprüft und mit gegensätzlichen Auffassungen beantwortet haben und welche auch im zweimaligen Schriftenwechsel vor Obergericht ausführlich thematisiert worden waren.
2.5 Aufgrund von <ref-law> muss das angerufene Gericht die ihm unterbreiteten Fragen vollständig entscheiden (<ref-ruling> E. 2.3 S. 232; Urteil 4A_39/2010 vom 29. April 2010 E. 2.3; AUBERT/ MAHON, Petit commentaire de la Constitution fédérale de la Confédération Suisse, 2003, N 4. zu <ref-law>; BIAGGINI, Kommentar Bundesverfassung der Schweizerischen Eidgenossenschaft, N. 12 zu <ref-law>). Eine Rechtsmittelinstanz kann eine Sache an die Vorinstanz zurückweisen, damit diese Fragen abkläre und beantworte, die rechtserheblich sind, aber bisher nicht (rechtsgenüglich) abgeklärt und beantwortet worden sind; die Rechtsmittelinstanz hat einen gewissen Ermessensspielraum darin, ob sie solche Fragen selber abklären und direkt entscheiden oder die Sache an die Vorinstanz zurückweisen will. Hier geht es aber nicht um Fragen, welche die Vorinstanzen nicht abgeklärt und beantwortet hätten. Vielmehr haben die kommunalen Instanzen bereits entschieden, dass der Beschwerdeführer ihre Anforderungen nicht erfülle und diese mit dem BGBM vereinbar seien, während der Regierungsrat das Gegenteil entschied. Die Parteien haben dem Obergericht diese Fragen zur Entscheidung unterbreitet. Es verletzt die Rechtsgewährleistungspflicht (<ref-law>), wenn das Obergericht diese ihm unterbreitete Frage nicht beantwortet, sondern die Sache an die Städtischen Werke zurückweist, damit diese die Frage nochmals beantworten, welche sie bereits beantwortet haben und welche Thema des ganzen Rechtsmittelverfahrens gebildet hat.
2.6 Die Rückweisung verstösst auch gegen <ref-law>, wonach über Beschränkungen des Zugangs zum freien Markt in einem raschen Verfahren zu entscheiden ist. Der Beschwerdeführer hat sein Gesuch am 8. August 2007 gestellt. Das Verfahren hat bis zum Entscheid des Obergerichts mehr als drei Jahre gedauert. Das ist zwar nicht auf übermässige Verfahrensdauern vor den einzelnen beteiligten Instanzen zurückzuführen. Trotzdem kann diese Verfahrensdauer insgesamt nicht als rasch bezeichnet werden. Wenn nun das Obergericht die Sache noch einmal zurückweist, damit die Vorinstanzen etwas beantworten, was sie bereits beantwortet haben, dann führt dies zu einer unnötigen Verfahrensverlängerung und verstösst gegen das Raschheitsgebot.
2.7 Der Beschwerdeführer stellt im Hauptantrag das reformatorische Begehren, es sei ihm die nachgesuchte Bewilligung zu erteilen. Es fragt sich, ob darauf eingetreten werden kann.
Ausgangspunkt des Verfahrens bildet hier die Verfügung der Städtischen Werke, welche die beantragte Bewilligung verweigerten. Vor dem Regierungsrat stellte der Beschwerdeführer den reformatorischen Antrag auf Erteilung der Bewilligung. Die Stadt wiederum beantragte vor Obergericht die Bestätigung ihres Entscheids, mithin die Verweigerung der Bewilligung. Erteilung bzw. Verweigerung der Bewilligung bildete somit Streitgegenstand vor Obergericht. Das Bundesgericht kann aufgrund der Akten den von der Vorinstanz noch nicht vollständig festgestellten Sachverhalt vervollständigen (<ref-law>), selber über die Bewilligungserteilung reformatorisch entscheiden (<ref-law>) und dabei im Rahmen des Streitgegenstands auch rechtserhebliche Fragen beantworten, welche von der Vorinstanz nicht beantwortet worden sind (<ref-ruling> E. 3.4.4 und 4.1 S. 366).
3. 3.1 Unbestritten verfügt der Beschwerdeführer über eine Bewilligung für Installationsarbeiten in der Gemeinde A._, wo er niedergelassen ist. Er hat damit nach Art. 2 Abs. 1 und 3 BGBM grundsätzlich Anspruch darauf, auch in Schaffhausen Installationsarbeiten durchführen zu können. Gemäss <ref-law> (in der Fassung vom 16. Dezember 2005, in Kraft seit 1. Juli 2006) gilt die Regelung von A._ als gleichwertig mit derjenigen von Schaffhausen. Diese Regelung, welche eine widerlegbare Vermutung aufstellt, gilt als Eckpfeiler für ein wirksames Binnenmarktgesetz (vgl. Botschaft vom 24. November 2004 über die Änderung des Binnenmarktgesetzes, BBl 2005 478 Ziff. 1.4.2.3, 481 Ziff. 2.1, 485 Ziff. 2.6; <ref-ruling> E. 2.1 S. 17 mit Hinweis auf die erwähnte Botschaft).
3.2 Nach <ref-law> kann dem Beschwerdeführer der Zugang zur Tätigkeit in Schaffhausen nicht verweigert, sondern nur mit Auflagen oder Bedingungen ausgestaltet werden, sofern diese gleichermassen auch für ortsansässige Personen gelten, zur Wahrung überwiegender öffentlicher Interessen unerlässlich und verhältnismässig sind. Nicht verhältnismässig sind Beschränkungen insbesondere wenn u.a. der hinreichende Schutz überwiegender öffentlicher Interessen bereits durch Vorschriften des Herkunftsorts erreicht wird oder durch die praktische Tätigkeit gewährleistet werden kann, welche der Anbieter am Herkunftsort ausgeübt hat (Art. 3 Abs. 2 lit. a und d BGBM).
3.3 Die Stadt Schaffhausen geht offensichtlich davon aus, dass der Beschwerdeführer den Nachweis seiner Fachkundigkeit erbringen müsste. Sie verkennt damit die gesetzliche Rollenverteilung: Da der Beschwerdeführer nach <ref-law> grundsätzlich Anspruch auf die Bewilligung hat und die Stadt ihm diesen Anspruch gestützt auf <ref-law> einschränken will, liegt es vielmehr an ihr, nachzuweisen, dass die Voraussetzungen für eine solche Einschränkung erfüllt sind (MANUEL BIANCHI DELLA PORTA, in: Commentaire romand, Droit de la concurrence, 2002, N. 34 zu <ref-law>).
3.4 Aktenkundig verfügt der Beschwerdeführer seit nunmehr über zwanzig Jahren über eine Konzession für die Ausführung von Wasserinstallationen in A._. Aufgrund der in <ref-law> enthaltenen Vermutung wäre es Sache der Stadt Schaffhausen, den Nachweis zu erbringen, dass die Zugangsvorschrift der Gemeinde A._ nicht gleichwertig ist. Solange diese Vermutung nicht umgestossen wird, ist aufgrund von <ref-law> auch der Schutz öffentlicher Interessen hinreichend gewährleistet und bleibt für eine zusätzliche Prüfung kein Raum (<ref-ruling> E. 2.4 S. 19). <ref-ruling>, auf den sich die Stadt Schaffhausen beruft, ist insoweit durch die geänderte Gesetzgebung überholt.
3.5 Ebenso trägt die Stadt Schaffhausen die Begründungs- und Beweislast dafür, dass die langjährige Berufspraxis des Beschwerdeführers den Schutz nicht gewährleistet (<ref-law>). Dafür müssten zumindest konkrete Anhaltspunkte vorliegen, dass der Bewerber die Anforderungen nicht (mehr) erfüllt (vgl. <ref-ruling> E. 2.4 S. 19). Gemäss Bestätigung der Bauverwaltung A._ vom 30. Juni 2008 wurden die Arbeiten durch den Beschwerdeführer stets zur Zufriedenheit ausgeführt. Zwar handelt es sich dabei nicht um einen Nachweis durch eine fachkundige Installationskontrolle, aber es ist doch anzunehmen, dass in einer relativ kleinen Gemeinde wie A._ der Bauverwaltung allfällige Beanstandungen bekannt wären. Die Stadt Schaffhausen hat im vorinstanzlichen Verfahren einen einzigen Vorfall erwähnt, bei welchem der Beschwerdeführer angeblich eine unsachgemässe Installation vorgenommen haben soll. Der Beschwerdeführer hat sich in seiner Duplik vor der Vorinstanz ausführlich mit diesem Vorwurf auseinandergesetzt. In der Beschwerdeantwort vor Bundesgericht beschränkt sich die Stadt darauf, diese Vorwürfe zu wiederholen, ohne sich mit den Ausführungen des Beschwerdeführers in der vorinstanzlichen Duplik auseinanderzusetzen. Der Nachweis, dass die langjährige praktische Tätigkeit des Beschwerdeführers das öffentliche Interesse nicht gewährleiste, ist damit nicht erbracht.
3.6 Der Beschwerdeführer hat deshalb Anspruch auf Erteilung der Bewilligung. Sollten sich in der Folge allenfalls Mängel an den vom ihm ausgeführten Arbeiten zeigen, so bleibt es der Stadt Schaffhausen unbenommen, die in den anwendbaren Vorschriften vorgesehenen Massnahmen zu treffen.
4. Die Beschwerde ist damit gutzuheissen, und das angefochtene Urteil der Vorinstanz ist aufzuheben. Die Stadt Schaffhausen ist anzuweisen, dem Beschwerdeführer die Installationsbewilligung für Wasserinstallationen auf dem Versorgungsgebiet der Städtischen Werke Schaffhausen und Neuhausen am Rheinfall zu erteilen.
Die unterliegende Stadt Schaffhausen trägt keine Kosten (Art. 66 Abs. 1 und 4 BGG), hat aber dem obsiegenden Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung auszurichten (<ref-law>). Im Übrigen ist die Sache zur Neuregelung der Kosten- und Entschädigungsfolgen des kantonalen Verfahrens an die Vorinstanz zurückzuweisen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid des Obergerichts des Kantons Schaffhausen vom 26. November 2010 aufgehoben. Die Stadt Schaffhausen wird angewiesen, dem Beschwerdeführer die Installationsbewilligung für Wasserinstallationen auf dem Versorgungsgebiet der Städtischen Werke Schaffhausen und Neuhausen am Rheinfall zu erteilen.
2. Es werden keine Gerichtskosten erhoben.
3. Die Stadt Schaffhausen hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4. Die Angelegenheit geht an das Obergericht des Kantons Schaffhausen zu neuem Entscheid über die Kosten- und Entschädigungsfolgen im vorinstanzlichen Verfahren.
5. Dieses Urteil wird dem Beschwerdeführer, den Städtischen Werken Schaffhausen und Neuhausen am Rheinfall, der Stadt Schaffhausen, dem Regierungsrat sowie dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 3. Mai 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger