Sachverhalt: A. X._ betrieb in der St. Galler Innenstadt seit dem Jahre 2002 ein Restaurant, welches etwa über 90 Sitzplätze verfügte. Am 1. Oktober 2008 traten die Regelungen zum Schutz vor dem Passivrauchen (Art. 52quater und Art. 52quinquies) des Gesundheitsgesetzes des Kantons St. Gallen vom 28. Juni 1979 (GesG; sGS 311.1) in Kraft. Danach ist das Rauchen in allgemein zugänglichen, geschlossenen Räumen verboten, ausgenommen in sogenannten Rauchzimmern. Unter bestimmten Voraussetzungen konnten gastgewerbliche Betriebe als Raucherbetriebe geführt werden. B. Nach Inkrafttreten des GesG führte die Polizei in der Stadt St. Gallen Kontrollen durch. Dabei stellte sie bei X._ mehrmals Verstösse gegen das GesG fest: Am 2., 3. und 4. Oktober sowie am 15. und 17. November 2008 wurden rauchende Gäste angetroffen; dabei standen Aschenbecher bzw. Unterteller auf den Tischen. Am 14. Januar 2009, dem letzten Kontrolltag, sprach die Polizei Ordnungsbussen gegen rauchende Gäste aus. Auf den Tischen lagen Merkblätter, welche die Gäste auf das geltende Rauchverbot aufmerksam machten; sie trugen gleichzeitig den Hinweis, die Gäste sollten einen Aschenbecher bestellen, falls sie trotz des Verbots im Lokal rauchen wollten, und sie könnten dabei gebüsst werden. Mit Verfügung vom 21. Januar 2009 entzog die Stadtpolizei X._ das Gastwirtschaftspatent mit sofortiger Wirkung; ausserdem wurde einem allfälligen Rekurs die aufschiebende Wirkung entzogen. X._ musste das Lokal ab dem 30. Januar 2009 geschlossen halten; mittlerweile wird das Lokal von einem anderen Gastwirt geführt. Gegen die Verfügung vom 21. Januar 2009 erhob X._ Beschwerde beim Volkswirtschaftsdepartement des Kantons St. Gallen. Dessen abweisenden Entscheid stützte das Verwaltungsgericht. C. X._ beantragt vor Bundesgericht, den Entscheid des Verwaltungsgerichts des Kantons St. Gallen vom 19. August 2009 aufzuheben und festzustellen, dass ihm das Gastwirtschaftspatent zu Unrecht entzogen wurde, eventuell die Sache zur Neubeurteilung ans Verwaltungsgericht zurückzuweisen. Das Verwaltungsgericht und die Direktion Soziales und Sicherheit der Stadt St. Gallen beantragen, die Beschwerde abzuweisen. Das Volkswirtschaftsdepartement des Kantons St. Gallen verzichtet auf eine Stellungnahme. 