Sachverhalt:
A. X._ (geb. 1957) ist in A._ (ZH) - seinen Angaben zufolge - seit 1999 als Heilpraktiker tätig. Am 4. Dezember 2007 bescheinigte ihm das Departement Gesundheit des Kantons Appenzell Ausserrhoden, dass er die Zulassungsprüfung als Heilpraktiker mit Erfolg bestanden habe und die gesetzlichen Voraussetzungen für die Ausübung des Heilpraktikerberufes erfülle. Somit sei er berechtigt, diese Tätigkeit im Kanton Appenzell Ausserrhoden auszuüben und dabei die Bezeichnung "kantonal approbierter Heilpraktiker" in seinen Auskündungen zu führen. Am 20. Dezember 2007 bewilligte das erwähnte Departement X._ auch die Durchführung von intra- und subkutanen Injektionen im Kanton Appenzell Ausserrhoden.
B. Am 24. Dezember 2008 ersuchte X._ die Gesundheitsdirektion des Kantons Zürich, seine Approbation als Heilpraktiker mit Injektionsbewilligung des Kantons Appenzell Ausserrhoden im Kanton Zürich vollumfänglich anzuerkennen und ihm insoweit die selbständige Berufsausübung zu bewilligen. Am 30. März 2009 wies die Gesundheitsdirektion das Gesuch ab. Es hielt gleichzeitig fest, dass X._ die heilpraktische Tätigkeit im bewilligungsfreien Bereich weiterhin gestattet sei.
X._ wandte sich gegen die Verfügung der Gesundheitsdirektion erfolglos an das Verwaltungsgericht des Kantons Zürich.
C. Mit Beschwerde vom 22. Januar 2010 stellt X._ dem Bundesgericht das Rechtsbegehren, das in dieser Sache zuletzt ergangene Urteil des Verwaltungsgerichts vom 5. November 2009 aufzuheben. Wie bei der Vorinstanz beantragt er zudem, seine Approbation als Heilpraktiker mit Injektionsbewilligung des Kantons Appenzell Ausserrhoden im Kanton Zürich anzuerkennen und damit die selbständige Verrichtung heilpraktischer Tätigkeiten mindestens im gleichen Umfange zu bewilligen, insbesondere "intra- und subkutane Injektionen (Stoffinjektionen), Entnahme von Blutproben, Ausübung der Akupunktur und Diagnostik und Differentialdiagnostik im für die Heilpraxis erforderlichen Rahmen". Eventuell sei die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen.
Die Gesundheitsdirektion und das Verwaltungsgericht des Kantons Zürich stellen den Antrag, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Binnen der vom Bundesgericht auf Antrag eingeräumten Frist nahm X._ am 30. April 2010 zur Vernehmlassung der Vorinstanzen Stellung. Die Gesundheitsdirektion und das Verwaltungsgericht verzichteten in der Folge auf eine weitere Stellungnahme.

Erwägungen:
1. Die fristgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten ist gegen den kantonal letztinstanzlichen Endentscheid des Verwaltungsgerichts grundsätzlich zulässig (vgl. Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2, Art. 90 und Art. 100 BGG). Es ist kein Ausschlussgrund nach Art. 83 BGG gegeben. Auch wenn es darum geht, ob der Beschwerdeführer fachliche oder persönliche Anforderungen für die Ausübung bestimmter Tätigkeiten erfüllt, greift Art. 83 lit. t BGG nicht, da nicht Fähigkeitsbewertungen als solche zur Debatte stehen (vgl. BGE 2C_772/2009 vom 31. August 2010 E. 1.2; Urteil des Bundesgerichts 2C_655/2009 vom 23. März 2010 E. 1; je mit Hinweis). Mangels Rechtsschutzinteresses nach Art. 89 Abs. 1 BGG ist allerdings insoweit nicht auf die Beschwerde einzutreten, als damit die Bewilligung von Tätigkeiten verlangt wird, die bereits erlaubt sind. Dabei handelt es sich - entsprechend der Vernehmlassung der Zürcher Gesundheitsdirektion - um die Diagnosestellung im Tätigkeitsbereich als Heilpraktiker, der dem Beschwerdeführer nicht untersagt wurde.
2. Der Beschwerdeführer macht eine Verletzung der persönlichen Freiheit und der Wirtschaftsfreiheit, die gemäss Art. 106 Abs. 2 BGG substanziiert zu rügen ist, geltend und bezieht sich mit den gleichen Argumenten auch auf das Bundesgesetz vom 6. Oktober 1995 über den Binnenmarkt (Binnenmarktgesetz, BGBM; SR 943.02).
Gemäss Art. 2 Abs. 4 BGBM (in der seit 1. Juli 2006 geltenden Fassung vom 16. Dezember 2005; AS 2006 2363 ff.) hat jede Person, die eine Erwerbstätigkeit rechtmässig ausübt, das Recht, sich zwecks Ausübung dieser Tätigkeit auf dem gesamten Gebiet der Schweiz niederzulassen und diese Tätigkeit unter Vorbehalt von Art. 3 BGBM nach den Vorschriften des Ortes der Erstniederlassung auszuüben. Dies gilt auch, wenn die Tätigkeit am Ort der Erstniederlassung aufgegeben wird. Nach Art. 2 Abs. 5 BGBM gelten die kantonalen bzw. kommunalen Marktzugangsordnungen insoweit als gleichwertig.
Art. 3 Abs. 1 BGBM zufolge darf ortsfremden Anbietern der freie Zugang zum Markt nicht verweigert werden. Beschränkungen sind in Form von Auflagen oder Bedingungen auszugestalten und nur zulässig, wenn sie gleichermassen auch für ortsansässige Personen gelten (lit. a), zur Wahrung überwiegender öffentlicher Interessen unerlässlich sind (lit. b) und verhältnismässig sind (lit. c). Beschränkungen, die demnach zulässig sind, dürfen in keinem Fall eine verdeckte Marktzutrittsschranke zu Gunsten einheimischer Wirtschaftsinteressen enthalten (Art. 3 Abs. 3 BGBM). Kantonale oder kantonal anerkannte Fähigkeitsausweise zur Ausübung einer Erwerbstätigkeit gelten auf dem gesamten Gebiet der Schweiz, sofern sie nicht Beschränkungen nach Art. 3 BGBM unterliegen (Art. 4 Abs. 1 BGBM).
3. Die Gesundheitsdirektion des Kantons Zürich ist der Auffassung, dass die Kantone Zürich und Appenzell Ausserrhoden im interessierenden Bereich keine gleichwertigen Marktzugangsordnungen haben. Deshalb seien die Bewilligungen, die der Beschwerdeführer im zuletzt genannten Kanton erhalten habe, nicht auch im Kanton Zürich anzuerkennen bzw. könne ihm dieser keine entsprechende Berufsausübungsbewilligung erteilen. Denn Injektionen dürften im Kanton Zürich im Rahmen der selbständigen Berufsausübung nur von Inhabern einer Berufsausübungsbewilligung als Arzt oder eines Diploms der Krankenpflege verabreicht werden. Pflegefachpersonen dürften Injektionen zudem ausschliesslich auf ärztliche Verordnung hin ausführen. Im Übrigen würde der Beschwerdeführer auch nicht die notwendige Vertrauenswürdigkeit aufweisen, so dass ihm ebenfalls aus diesem Grunde die verlangte Bewilligung zu verweigern sei.
Das Verwaltungsgericht befasst sich ausführlich mit der Frage, ob es mit dem Binnenmarktgesetz vereinbar sei, für die Durchführung von Injektionen und Blutentnahmen eine Berufsausübungsbewilligung als Arzt oder ein Diplom der Krankenpflege zu verlangen. Obwohl es dazu neigt, diese Frage zu bejahen, lässt es sie letztlich offen und weist das Begehren des Beschwerdeführers wegen mangelnder Vertrauenswürdigkeit ab.
4. 4.1 Gemäss § 3 Abs. 1 des Zürcher Gesundheitsgesetzes vom 2. April 2007 (GesG/ZH) benötigt namentlich derjenige einer Bewilligung der Gesundheitsdirektion, der fachlich eigenverantwortlich sowie berufsmässig oder im Einzelfall gegen Entgelt Krankheiten, Verletzungen oder sonstige gesundheitliche Beeinträchtigungen nach den Erkenntnissen der anerkannten Wissenschaften oder im Rahmen der wissenschaftlichen Forschung feststellt oder behandelt (lit. a). Dasselbe gilt für Personen, die instrumentale Eingriffe in den Körperöffnungen oder körperverletzend unter der Haut vornehmen (lit. e). Um die Bewilligung zu erhalten, muss die gesuchstellende Person unter anderem gemäss § 4 Abs. 1 lit. c GesG/ZH vertrauenswürdig sein. Auch das Gesetz des Kantons Appenzell Ausserrhoden vom 25. April 1965 über das Gesundheitswesen (aGesG/AR), das zwar am 1. Januar 2008 durch ein neues Gesundheitsgesetz vom 25. November 2007 ersetzt wurde, aber noch im Zeitpunkt der Bewilligung der interessierenden Tätigkeiten in diesem Kanton galt, gestattet die Ausübung einer Heiltätigkeit nur vertrauenswürdigen Personen (Art. 15 aGesG/AR).
Das Bundesgericht hat die Vermutung der Gleichwertigkeit von Fähigkeitsausweisen gemäss Art. 4 Abs. 1 BGBM auch auf die persönlichen Voraussetzungen wie die Vertrauenswürdigkeit bezogen. Denn es darf angenommen werden, dass sich dieses Kriterium von Kanton zu Kanton nicht wesentlich unterscheidet (vgl. <ref-ruling> E. 5b S. 283 f.; 322 E. 4b S. 332; <ref-ruling> E. 4b S. 62). Zudem besteht seit der Revision des Binnenmarktgesetzes im Jahr 2005 bzw. 2006 nach Art. 2 Abs. 5 BGBM explizit die Vermutung der Gleichwertigkeit kantonaler Marktzugangsregelungen (<ref-ruling> E. 2.1 S. 17). Diese Vermutung verlöre ihren Sinn, müsste die Befähigung des Betreffenden - einem neuerlichen Zulassungsverfahren gleich - vom Bestimmungskanton abermals individuell überprüft werden. Sie wird allerdings widerlegt, wenn konkrete Anhaltspunkte dafür bestehen, dass die Voraussetzungen für die seinerzeitige Marktzulassung im Herkunftskanton gar nie erfüllt wurden oder zwischenzeitlich nicht mehr erfüllt werden (<ref-ruling> E. 2.4 S. 19; Urteil 2C_68/2009 vom 14. Juli 2009 E. 6.3).
4.2 Die Vorinstanz führt aus, der Vorwurf der mangelnden Vertrauenswürdigkeit stütze sich auf Vorfälle, die sich im Kanton Zürich zugetragen haben und den Behörden im Kanton Appenzell Ausserrhoden daher mit hoher Wahrscheinlichkeit nicht bekannt waren oder - soweit sich die Vorfälle nach der Bewilligungserteilung durch den letztgenannten Kanton ereigneten - nicht bekannt sein konnten. Mit Blick auf die dem Beschwerdeführer entgegengehaltenen Vorfälle, die nicht oder erst später zu Strafregistereinträgen führten, leuchtet das ohne Weiteres ein. Zur Belegung seiner Vertrauenswürdigkeit musste dieser im Kanton Appenzell Ausserrhoden zwar nach Art. 15 Abs. 2 aGesG/AR ein Leumundszeugnis vorlegen. Dieses bezieht sich jedoch regelmässig bloss auf im Zeitpunkt der Ausstellung nicht gelöschte Vorstrafen (vgl. <ref-ruling> E. 2b S. 189 und Dokument des Bundesamts für Justiz vom 15. September 1986, publ. in: VPB 51/1987 Nr. 46). Der Beschwerdeführer behauptet denn auch nicht, der Kanton Appenzell Ausserrhoden habe in voller Kenntnis sämtlicher Umstände entschieden. Demnach ist entgegen der Ansicht des Beschwerdeführers nicht zu beanstanden, wenn die Zürcher Behörden eine eigene Prüfung der Vertrauenswürdigkeit vorgenommen haben, zumal sich diese - wie die Vorinstanz richtig bemerkt - nicht bloss anhand von Vorstrafen beurteilt, die im Strafregister eingetragen sind.
Ob sich eine entsprechende Prüfungspflicht bzw. -kompetenz des Kantons Zürich bereits aus Art. 35 Abs. 2 und 3 des Bundesgesetzes vom 23. Juni 2006 über die universitären Medizinalberufe (MedBG; SR 811.11) als lex specialis ergibt, wovon die Zürcher Gesundheitsdirektion ausgeht, kann nach dem Dargelegten offen gelassen werden.
5. 5.1 Die Vorinstanzen werfen dem Beschwerdeführer diverse Verstösse gegen die Heilmittel- und Gesundheitsgesetzgebung vor. Nach verschiedenen Verwarnungen bzw. Interventionen der Zürcher Behörden zwischen 1988 und 2005 wurde der Beschwerdeführer am 7. Mai 2008 durch das Statthalteramt des Bezirks Hinwil mit Fr. 20'000.-- gebüsst. Dem lagen zugrunde namentlich die unerlaubte Abgabe von Medikamenten, die Ausführung unbewilligter Tätigkeiten im Heilbereich und die Erweckung des Anscheins, zur Berufsausübung als Arzt berechtigt zu sein. Das Statthalteramt bezeichnete das Verschulden angesichts der zahlreichen früheren Interventionen der Behörden "als nicht mehr leicht". Laut Verwaltungsgericht habe der Beschwerdeführer danach noch gegenüber Drittpersonen versucht, sein Verhalten zu verharmlosen. Zudem erging wegen irreführender Auskündigung am 30. September 2009 erneut eine Strafverfügung gegen ihn.
5.2 Der Beschwerdeführer meint, wegen einer einmaligen gesundheitsrechtlichen Verfehlung dürfe ihm der Marktzugang nicht verweigert werden. Seit Jahren behandle er rund 2500 Patienten, ohne dass es zu einer Beanstandung wegen konkreter Gesundheitsgefährdungen gekommen sei. Zudem dürfe ihm die begehrte Bewilligung nur vorenthalten werden, wenn ihm das Statthalteramt zusätzlich zur Busse ein Berufsverbot auferlegt hätte. Da sein Fehlverhalten bloss mit einer Busse geahndet worden sei, könne die spätere Bewilligungsverweigerung nicht mehr hierauf gestützt werden. Sonst liefe das auf eine unzulässige doppelte Sanktionierung hinaus.
5.3 Dass der Beschwerdeführer bereits vom Statthalteramt rechtskräftig sanktioniert wurde, steht der Bewilligungsverweigerung nicht entgegen. Denn bei Letzterer handelt es sich nicht um eine Zusatzstrafe (vgl. <ref-ruling> E. 1a und b S. 29 f.; Urteil des Bundesgerichts 2P.274/2004 vom 13. April 2005 E. 3.2). Vielmehr geht es darum, die öffentliche Ordnung und Gesundheit zu bewahren. Um dies bestmöglich zu gewährleisten, muss die Vertrauenswürdigkeit sowohl gegenüber den Patienten als auch gegenüber den Behörden bestehen (erwähntes Urteil 2C_655/2009 E. 2). Die Verweigerung der Bewilligung setzt auch nicht voraus, dass zuvor ein Berufsverbot als Nebenstrafe auferlegt worden ist.
Wie die Vorinstanz sodann ausführlich darlegt, wurde dem Beschwerdeführer nicht ein einmaliger Verstoss vorgeworfen, sondern mehrfache, teilweise wiederholte Verstösse. Da es sich nicht um bloss geringfügige Verfehlungen handelt und diese zudem den beruflichen Bereich betreffen, durften die Vorinstanzen aufgrund der Gesamtumstände von einer derzeit fehlenden Vertrauenswürdigkeit ausgehen. Daran ändert nichts, dass bisher keine konkreten Gesundheitsgefährdungen bekannt geworden sind. Diese gilt es unter anderem durch vorbeugende Massnahmen zu vermeiden. Der Beschwerdeführer will mit der begehrten Bewilligung denn auch zusätzliche, sensiblere medizinische Tätigkeiten ausüben können. Bisher war er im Kanton Zürich nur in weniger problematischen Bereichen tätig. Soweit er teilweise seine Kompetenzen überschritten hatte, hat er immerhin die Gesundheit von Klienten abstrakt gefährdet.
Der Beschwerdeführer verweist zwar darauf, dass er sich im Kanton Appenzell Ausserrhoden "wohlverhalten" habe und deshalb dort über eine Unbedenklichkeitsbescheinigung ("letter of good understanding") verfüge. Auf den Vorhalt der Zürcher Gesundheitsdirektion, dass nicht ersichtlich sei, inwiefern er im Kanton Appenzell Ausserrhoden jemals tätig geworden sei, hat der Beschwerdeführer jedoch nicht geantwortet. Über entsprechende Bewilligungen verfügt er dort auch erst seit Dezember 2007. Zudem äussert sich die Appenzeller Unbedenklichkeitsbescheinigung nicht zum Verhalten des Beschwerdeführers im Kanton Zürich. Daher durfte die Vorinstanz ihr kein Gewicht beimessen.
Unbehelflich ist auch der Einwand des Beschwerdeführers, die Berufung auf rechtsstaatliche Garantien im strafrechtlichen Verfahren dürfe nicht als Verharmlosung seines Fehlverhaltens bezeichnet werden. Denn der angefochtene Entscheid enthält keine diesbezüglichen Vorwürfe. Vielmehr wird ihm Verharmlosung nach Verhängung der Busse vorgehalten. Darauf geht der Beschwerdeführer nicht ein.
Soweit der Beschwerdeführer schliesslich in seiner Replik vom 30. April 2010 darauf hinweist, in elektronischen Verzeichnissen würden zahlreiche "China-Ärzte" auf dem Zürcher Gesundheitsmarkt auskünden, ohne dass die Zürcher Gesundheitsdirektion dagegen vorginge, ist dieses Vorbringen, soweit überhaupt relevant, als Novum aus dem Recht zu weisen. Weder ist ersichtlich, dass der Beschwerdeführer dies schon bei den Vorinstanzen vorgebracht hatte, noch dient die Replik dazu, Rügen zu erheben, die bereits in der Beschwerdeschrift selbst fristgerecht hätten erhoben werden können (vgl. <ref-ruling> E. 2.2 S. 21; <ref-ruling> E. 3 S. 395; <ref-ruling> E. 3.3.4 S. 47; je mit Hinweisen).
5.4 Weitere (substanziierte) Rügen macht der Beschwerdeführer in Bezug auf die Vertrauenswürdigkeit und die darauf gestützte Bewilligungsverweigerung nicht geltend, weshalb sich zusätzliche Ausführungen erübrigen (vgl. Art. 42 Abs. 2 BGG sowie <ref-ruling> E. 1.4.1 und 1.4.2 S. 254). Es kann ergänzend auf die zutreffenden und sorgfältigen Ausführungen der Vorinstanz verwiesen werden. Insoweit ist auch der Vorwurf der Verletzung der Wirtschaftsfreiheit und der persönlichen Freiheit nicht begründet. Einschränkungen dieser Freiheiten wegen mangelnder Vertrauenswürdigkeit sind nämlich zulässig (vgl. <ref-ruling>; erwähntes Urteil 2P.274/2004 E. 3.2 mit Hinweisen) und der Beschwerdeführer hat nicht dargelegt, inwiefern hier dennoch ein Grundrechtsverstoss gegeben sein soll. Namentlich mit Blick darauf, dass der Beschwerdeführer seine bisher erlaubte Tätigkeit im Kanton Zürich fortführen kann und die Vorinstanz darauf hinweist, ihm dürfe sein früheres Verhalten "nicht ewig" vorgeworfen werden, bei künftiger Bewährung könne er einen neuen Antrag stellen, erweist sich die aktuelle Bewilligungsverweigerung auch als verhältnismässig.
Nach dem Dargelegten ist der Entscheid der Vorinstanz, die begehrte Bewilligung mangels Vertrauenswürdigkeit vorerst zu verweigern, zu bestätigen. Damit braucht vorliegend nicht mehr darauf eingegangen zu werden, ob die Zürcher Behörden gegenüber den Regelungen des Kantons Appenzell Ausserrhoden zusätzliche bzw. andere fachliche Anforderungen für die interessierenden Heiltätigkeiten stellen durften.
6. Demzufolge ist die Beschwerde unbegründet und daher abzuweisen, soweit darauf einzutreten ist. Diesem Ausgang entsprechend hat der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65 f. BGG). Parteientschädigungen werden nicht geschuldet (Art. 68 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Zürich, 3. Kammer, schriftlich mitgeteilt.
Lausanne, 4. Dezember 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Merz