Sachverhalt:
A. X._ betrieb in der St. Galler Innenstadt seit dem Jahre 2002 ein Restaurant, welches etwa über 90 Sitzplätze verfügte. Ende August 2009 schloss er sein Lokal. Anlass dazu bildete - so seine Ausführungen - der Besucher- bzw. Konsumationsrückgang wegen des kantonalen Rauchverbots.
B. Am 9. Juli 2008 beantragte X._ bei der Stadtpolizei St. Gallen, ihm eine Ausnahmebewilligung im Sinne von Art. 52quinquies des Gesundheitsgesetzes des Kantons St. Gallen vom 28. Juni 1979 (GesG; sGS 311.1) zu erteilen, damit er sein Restaurant als Raucherbetrieb führen könne. Die Stadtpolizei wies das Gesuch ab. Die dagegen gerichtete Beschwerde an das Verwaltungsgericht des Kantons St. Gallen blieb erfolglos.
C. X._ beantragt vor Bundesgericht, den Entscheid des Verwaltungsgerichts des Kantons St. Gallen vom 19. August 2009 aufzuheben und festzustellen, dass ihm zu Unrecht die Führung eines Raucherbetriebs verweigert wurde, eventuell die Sache zur Neubeurteilung und Ergänzung des Sachverhalts ans Verwaltungsgericht zurückzuweisen. Das Verwaltungsgericht und das Gesundheitsdepartement des Kantons St. Gallen sowie die Direktion Soziales und Sicherheit der Stadt St. Gallen beantragen, die Beschwerde abzuweisen.

Erwägungen:
1. 1.1 Die Beschwerde ist innert der gesetzlichen Frist (<ref-law>) eingereicht worden und richtet sich gegen den Endentscheid (<ref-law>) einer letzten kantonalen Instanz (<ref-law>) in einer Angelegenheit des öffentlichen Rechts (<ref-law>), die unter keinen Ausschlussgrund nach <ref-law> fällt.
1.2 Der Beschwerdeführer macht geltend, dass er an einer Ausnahmebewilligung nicht mehr interessiert sei; er habe sein Restaurant infolge finanzieller Einbussen schliessen müssen, da ihm die Behörde keine Ausnahmebewilligung erteilt habe. Er sei aber trotzdem an einer Überprüfung des vorinstanzlichen Entscheids interessiert, da er durch die Verweigerung einer solchen Bewilligung einen erheblichen wirtschaftlichen Schaden erlitten habe.
Zwar ist zur Beschwerde nur legitimiert, wer u.a. ein schutzwürdiges aktuelles und praktisches Interesse an der Beurteilung seiner Eingabe hat (<ref-law>), doch verzichtet das Bundesgericht ausnahmsweise darauf, wenn sich die aufgeworfenen Fragen unter gleichen oder ähnlichen Umständen jederzeit wieder stellen können, eine rechtzeitige Überprüfung im Einzelfall kaum je möglich wäre und die Beantwortung wegen deren grundsätzlicher Bedeutung im öffentlichen Interesse liegt (<ref-ruling> E. 1.1 S. 81; Urteil 1C_89/2007 vom 13. Juli 2007 E. 1.3). Dies trifft auch auf den vorliegenden Fall zu: Aufgrund der dargelegten Sachlage rechtfertigt es sich, auf das aktuelle und praktische Interesse zu verzichten. Mit der Aufgabe des Lokals kann die Verweigerung der Erteilung einer Ausnahmebewilligung, welche nach Auffassung des Beschwerdeführers gerade Anlass zu dessen Schliessung bildete, nie rechtzeitig überprüft werden. Es liegt deshalb im öffentlichen Interesse, diese Verweigerung auf ihre Rechtmässigkeit zu überprüfen. Auf die Beschwerde ist grundsätzlich einzutreten.
1.3 Da der Beschwerdeführer wegen Aufgabe seines Lokals nicht mehr an einer Ausnahmebewilligung interessiert sei, beantragt er implizit festzustellen, dass deren Verweigerung zu Unrecht erfolgt sei. Feststellungsbegehren sind vor Bundesgericht nur dann zulässig, wenn das schutzwürdige Interesse nicht ebensogut mit einem rechtsgestaltenden Begehren gewahrt werden kann (<ref-ruling> E. 2c S. 303). Nach Aufgabe des Lokals kann der Beschwerdeführer seine Interessen mit einem rechtsgestaltenden Begehren nicht mehr wahrnehmen. Das Feststellungsbegehren ist deshalb zulässig.
1.4 Mit der Beschwerde kann u.a. die Verletzung von Bundesrecht (einschliesslich der verfassungsmässigen Rechte) gerügt werden (<ref-law>). Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es prüft die Verletzung von Grundrechten und von kantonalem Recht allerdings nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>).
2. Nach Art. 52quater Abs. 1 GesG ist das Rauchen in allgemein zugänglichen, geschlossenen Räumen verboten, ausgenommen in Rauchzimmern. Abs. 2 umschreibt die Räume, welche als allgemein zugänglich gelten. Abs. 3 hält schliesslich fest, dass Rauchzimmer Räume sind, die von anderen Räumen des Gebäudes und deren Belüftung und Entlüftung getrennt und als solche gekennzeichnet sein müssen sowie keinem anderen Zweck dienen. Nach Art. 52quinquies Abs. 1 GesG sind in gastgewerblichen Betrieben Rauchzimmer auf höchstens einem Drittel der Schankfläche in geschlossenen Räumen zulässig, wenn für diese Räume ein Patent für einen Betrieb nach dem kantonalen Gastwirtschaftsgesetz erteilt wurde (lit. a) und für angrenzende, allgemein zugängliche Räume der Schutz vor Passivrauchen gewährleistet ist, insbesondere wenn der Zugang über gastgewerblich genutzte Räume erfolgt (lit. b). Nach dessen Abs. 2 können gastgewerbliche Betriebe aufgrund einer Bewilligung der politischen Gemeinde als Raucherbetriebe geführt werden. Diese wird erteilt, wenn die Betreiberin oder der Betreiber den Nachweis erbringt, dass eine Trennung von Raucher- und Nichtraucherräumen nicht möglich oder unzumutbar ist und die Voraussetzungen nach Abs. 1 lit. a und b erfüllt sind.
3. Der Beschwerdeführer rügt zunächst eine Verletzung der Wirtschaftsfreiheit; diese werde durch die gesetzliche Regelung des Rauchverbots unverhältnismässig eingeschränkt. Er verlangt damit eine inzidente Normenkontrolle.
3.1 Nach <ref-law> ist die Wirtschaftsfreiheit gewährleistet. Dazu zählt insbesondere der freie Zugang und die freie Ausübung einer privatwirtschaftlichen Erwerbstätigkeit. Zunächst stellt sich die Frage, ob das Rauchen(-Lassen) der Gäste überhaupt in den sachlichen und personellen Schutzbereich der Wirtschaftsfreiheit eines Wirtes fällt und ob das Rauchverbot überhaupt einen Eingriff in diese darstellt: Das Rauchverbot in Restaurants, deren Haupttätigkeit im Angebot von Speisen und Getränken besteht, schränkt die Wirtschaftsfreiheit ihrer Betreiber nicht direkt ein (<ref-ruling> E. 7.4 S. 126; BGE 2C_195/2009 E. 3.2; BGE 2C_283/2009 E. 3.2; Andreas Auer, Le droit face à la political correctness: La constitutionnalité de l'initiative populaire genevoise "Fumée passive et santé", AJP 2006, S. 3 ff., 12 f.), jedenfalls solange ein Wirt nicht ein spezifisches Angebot für Raucher unterhalten will (vgl. Auer, a.a.O., S. 13). Ein indirekter Eingriff in die Wirtschaftsfreiheit kann allenfalls dann vorliegen, wenn mit dem Rauchverbot finanzielle Einbussen verbunden sind, weil die Kundschaft ausbleibt oder weil der Wirt verpflichtet wird, zusätzliche Aufwendungen zu tätigen.
3.2 Die Wirtschaftsfreiheit gilt nicht schrankenlos, sondern sie kann, sofern es sich um Massnahmen handelt, die sich nicht gegen den Wettbewerb richten (<ref-law>), gestützt auf <ref-law> eingeschränkt werden. Andernfalls wäre zusätzlich eine Bundesverfassungsnorm oder ein kantonales Regalrecht notwendig (<ref-law>); beides trifft vorliegend nicht zu.
Zu Recht bestreitet der Beschwerdeführer weder die gesetzliche Grundlage (Art. 52quater und 52quinquies GesG), das öffentliche Interesse (Schutz der Bevölkerung vor Passivrauch) noch die Geeignetheit eines Rauchverbots. Er rügt indes, dass "ein gänzliches Rauchverbot in gastgewerblichen Betrieben" weder erforderlich noch zumutbar sei. Der Beschwerdeführer übersieht allerdings, dass seine Prämisse, auf welche er seine Rügen stützt, falsch ist. Im Kanton St. Gallen gilt kein "gänzliches" Rauchverbot. Das kantonale Gesetz erlaubt, dass in Rauchzimmern geraucht werden darf, wobei für gastgewerblich genutzte Räume die Rauchzimmer auf ein Drittel der Schankfläche begrenzt werden. Schliesslich besteht sogar die Möglichkeit, dass ein Raucherbetrieb geführt werden kann, wenn die Voraussetzungen nach Art. 52quinquies Abs. 2 GesG erfüllt sind. Massnahmen, welche eine Trennung von Nichtrauchern und Rauchern vorsehen, sind zur Erreichung des Zieles "Schutz der Bevölkerung vor Passivrauch" erforderlich. Etwas anderes als eine durch bauliche Massnahmen vorgesehene Trennung, wie etwa nur getrennte Tische in demselben Raum, vermag diesem öffentlichen Interesse nicht gerecht zu werden. Mit der Möglichkeit entweder ein Fumoir einzubauen, einen rauchfreien Betrieb zu führen, wo indes im Freien geraucht werden kann, wie es beispielsweise in anderen Ländern vorgesehen ist und auch die Gäste des Beschwerdeführers praktiziert haben (siehe dazu auch Tobias Jaag/Markus Rüssli, Schutz vor Passivrauchen: verfassungsrechtliche Aspekte, AJP 2006, S. 21 ff., 28) oder unter bestimmten Voraussetzungen gar ein Raucherlokal zu führen, stellt der Gesetzgeber des Kantons St. Gallen auch mehrere alternative, mildere Massnahmen zur Verfügung (Jaag/Rüssli, a.a.O., S. 28). Welche von diesen Massnahmen schliesslich die mildere ist, hängt von der konkreten Situation ab. So kann allenfalls das Führen eines rauchfreien Restaurants, mit der Möglichkeit im Freien zu rauchen, aus Sicht des Wirts eine mildere Massnahme darstellen als das Einbauen eines Fumoirs. Sollten zudem die Massnahmen, welche eine bauliche Trennung vorsehen, im Sinne der Zweck-Mittel-Relation unzumutbar sein, hat der Gesetzgeber vorgesehen, dass unter bestimmten Voraussetzungen das Lokal als Raucherbetrieb geführt werden kann. Insofern ist die Wirtschaftsfreiheit durch die gesetzlichen Regelungen (Art. 52quater und 52quinguies GesG) nicht unverhältnismässig eingeschränkt und unter Berücksichtigung der nicht strittigen anderen Elemente von <ref-law> auch nicht verletzt.
Da für alle Gastwirte des Kantons St. Gallen, unabhängig davon, ob sie ein Luxusrestaurant, eine Brasserie, ein Bistro oder eine Bar betreiben, aufgrund der gesetzlichen Regelungen die gleichen Anforderungen gelten, ist nicht ersichtlich, inwiefern damit der Grundsatz der Gleichbehandlung der Konkurrenten verletzt worden wäre. Wenn der Eine im Einzelfall eine Ausnahmebewilligung erhält, wird damit nicht bezweckt, in den Wettbewerb einzugreifen, um diesen gegenüber anderen Wirten zu bevorzugen (vgl. <ref-ruling> E. 4b/aa S. 435 f.), sondern es handelt sich um ein Absehen einer zwar polizeilich gerechtfertigten (Fumoir), aber im Einzelfall nicht zumutbaren Massnahme. Insofern ist auch das Argument der Strukturbereinigung nicht geeignet, die Rechtmässigkeit der kantonalen Regelung in Frage zu stellen.
4. 4.1 Der Beschwerdeführer macht ferner geltend, dass erstens die Vorinstanzen den Begriff "zumutbar" nach Art. 52quinquies Abs. 2 GesG fehlerhaft konkretisiert und ihr Ermessensspielraum unterschritten hätten sowie auch nicht auf die Ursachen des Umsatzrückganges eingegangen seien. Im Übrigen seien die Kriterien nicht transparent gemacht worden, welche in vielen Fällen zu einer Ausnahmebewilligung geführt hätten; dies sei willkürlich. Zweitens verstosse die Verweigerung der Erteilung einer Ausnahmebewilligung gegen die Wirtschaftsfreiheit.
4.2 Das Bundesgericht überprüft nicht die richtige Anwendung des kantonalen Rechts, sondern nur, ob der kantonale Akt höherrangiges Recht verletzt hat (<ref-law>; <ref-ruling> E. 4.2.2 S. 158). Die Auslegung und Anwendung des kantonalen Rechts prüft das Bundesgericht nur unter dem Gesichtswinkel des Willkürverbots (<ref-law>; <ref-ruling> E. 4.2.2 S. 158). Dabei hat der Beschwerdeführer in der Beschwerde im Einzelnen darzulegen (Art. 42 Abs. 2 in Verbindung mit <ref-law>), inwiefern der angefochtene Entscheid willkürlich sein soll (vgl. <ref-ruling> E. 1 S. 203), d.h. an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 1.3 S. 261 mit Hinweisen).
Mit der ersten Rüge kritisiert der Beschwerdeführer lediglich die blosse Auslegung und die Anwendung von Art. 52quinquies Abs. 2 GesG. Er setzt sich nicht vertieft mit dem vorinstanzlichen Entscheid auseinander, sondern wiederholt lediglich, was er vor der Vorinstanz bereits vorgebracht hat. Inwiefern die Auslegung geradezu qualifiziert unrichtig, mithin willkürlich sein soll, wird aus den vorgebrachten Argumenten somit nicht ersichtlich. Insoweit ist deshalb auf die Beschwerde nicht einzutreten.
4.3 Der Beschwerdeführer rügt zudem, dass vorliegendenfalls die Verweigerung einer Ausnahmebewilligung die Wirtschaftsfreiheit verletze, d.h. sie weder erforderlich noch verhältnismässig im engeren Sinne sei, dass somit mildere Massnahmen (d.h. überhaupt keine Massnahmen) verfügt werden könnten und ein Missverhältnis zwischen den öffentlichen und den privaten Interessen bestehe. Der Beschwerdeführer verweist darauf, dass es in allernächster Nähe seines Betriebs genügend Lokale gebe, in denen entweder nur in Fumoirs oder überhaupt nicht geraucht werden dürfe. Zum Schutz der Nichtraucher sei es deshalb nicht erforderlich, seinen kleinen Betrieb ebenfalls noch rauchfrei zu halten.
Die Argumente des Beschwerdeführers vermögen nicht zu überzeugen: Ob eine Ausnahmebewilligung zu Recht oder zu Unrecht verweigert wurde, ist nicht eine Frage des Verhältnismässigkeitsprinzips, sondern eine solche, ob die gesetzlichen Voraussetzungen erfüllt sind oder nicht. Es geht somit um die richtige Anwendung von (unbestimmten) Gesetzesbegriffen (vgl. Ulrich Zimmerli, Der Grundsatz der Verhältnismässigkeit im öffentlichen Recht, ZSR 1978 II S. 1, 56), welche das Bundesgericht nicht bzw. nur auf Willkür hin überprüft (vgl. oben E. 4.2). Im Übrigen sind die vorgebrachten Argumente auch in der Sache unbehelflich: Nicht entscheidend ist, ob in der näheren Umgebung andere raucherfreie Restaurants oder solche mit Fumoir geführt werden. Denn das Gesundheitsgesetz stellt mit seinen generell-abstrakten Regelungen die gleichen Anforderungen an alle Personen, welche "gastgewerblich genutzte Räume" führen.
5. 5.1 Die Beschwerde erweist sich damit als unbegründet und ist abzuweisen, soweit darauf eingetreten wird.
5.2 Bei diesem Verfahrensausgang wird der Beschwerdeführer kostenpflichtig (Art. 66 Abs. 1 und Art. 65 BGG). Eine Parteientschädigung ist nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 23. Februar 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Errass