Sachverhalt:
A.
Der in Küsnacht im Kanton Zürich wohnhafte X._ ist Eigentümer der Liegenschaft Nr. xxx in Andermatt. Am 1. Juli 2011 trat dort das von der Offenen Dorfgemeinde Andermatt am 28. Oktober 2010 beschlossene "Reglement über den Tourismus in den Gemeinden Andermatt, Hospental und Realp" (im Folgenden: "Tourismusreglement") in Kraft. Dieses sieht u.a. vor, dass die drei Gemeinden eine "Beherbergungsgebühr" (auch für Zweitwohnungen, Ferienwohnungen und Ferienhäuser) erheben, welche an die Stelle der früheren Kurtaxen tritt.
B.
Am 31. August 2011 wandte sich X._ an den Gemeinderat Andermatt, äusserte Zweifel an der Anwendbarkeit des neuen Tourismusreglements auf seine Liegenschaft und ersuchte um Erlass einer anfechtbaren (Feststellungs-) Verfügung mit Rechtsmittelbelehrung.
Mit Schreiben vom 5. September 2011 stellte der Gemeinderat Andermatt X._ für den Zeitraum vom 1. Juni 2011 bis zum 31. Dezember 2011 eine Beherbergungsgebühr von Fr. 737.80 (zahlbar innert 30 Tagen) provisorisch in Rechnung. Das genannte Schreiben enthielt sodann folgenden Hinweis:
"Die definitive Veranlagungsverfügung inklusive der definitiven Rechnung sowie der Rechtsmittelbelehrung werden wir Ihnen zu einem späteren Zeitpunkt zustellen".
Hiegegen wandte sich X._ mit einer Verwaltungsbeschwerde an den Regierungsrat des Kantons Uri, wo er die Aufhebung der genannten Rechnung sowie die Aufhebung bzw. Abänderung von Teilen des Tourismusreglements beantragte. Mit Entscheid vom 20. März 2012 wies der Regierungsrat die Beschwerde ab, soweit er darauf eintrat; dies im Wesentlichen mit der Begründung, bei der provisorischen Rechnung vom 5. September 2011 handle es sich nicht um eine Verfügung und damit nicht um ein taugliches Anfechtungsobjekt. Somit entfalle auch eine akzessorische Normenkontrolle.
Mit Urteil vom 22. Februar 2013 wies das Obergericht des Kantons Uri (Verwaltungsrechtliche Abteilung) eine von X._ gegen den regierungsrätlichen Entscheid gerichtete Beschwerde ebenfalls ab.
C.
Mit Eingabe vom 20. März 2013 führt X._ "Beschwerde" beim Bundesgericht mit den Anträgen, das letztgenannte Urteil aufzuheben und das Verfahren an die Vorinstanz zurückzuweisen. Eventuell sei diese anzuweisen, das Verfahren zum Erlass eines Sachentscheides an den Regierungsrat Uri zurückzuweisen.
Die Erziehungsdirektion - für den Regierungsrat - sowie das Obergericht verzichten auf Vernehmlassung. Die Einwohnergemeinde Andermatt beantragt, die Beschwerde abzuweisen.

Erwägungen:
1.
1.1. Angefochten ist ein letztinstanzlicher kantonaler Endentscheid über eine Angelegenheit des öffentlichen Rechts, welche unter keinen der in <ref-law> genannten Ausschlussgründe fällt, weshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Art. 90 BGG). Als solche ist die "Beschwerde" vom 20. März 2013 denn auch entgegenzunehmen und zu behandeln; der Beschwerdeführer ist hierzu legitimiert (<ref-law>). Die Beschwerdeanträge sind zulässig, da der angefochtene Entscheid die Qualität der Rechnung vom 5. September 2011 (vorne lit. B) als anfechtbare Verfügung sowie eine Rechtsverweigerung verneint hat. Eine Gutheissung der vorliegenden Beschwerde könnte aber von Vornherein nur eine Rückweisung zur materiellen Beurteilung zur Folge haben. Soweit sich der Beschwerdeführer inhaltlich gegen das Tourismusreglement wendet, sprengt dies den Streitgegenstand (vgl. dazu <ref-ruling> E. 5 S. 174) und kann auf die Beschwerde nicht eingetreten werden.
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht kann die Verletzung von Bundesrecht und Völkerrecht gerügt werden (<ref-law>). Die Verletzung kantonalen Rechts ist hingegen vor Bundesgericht - abgesehen von den Fällen gemäss Art. 95 lit. c-e BGG - kein selbstständiger Rügegrund, sondern kann nur daraufhin überprüft werden, ob damit Bundesrecht verletzt wird, wozu namentlich auch eine willkürliche Anwendung kantonalen Rechts gehört (<ref-ruling> E. 2 S. 149; <ref-ruling> E. 2.4 S. 249).
Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (<ref-law>); dies setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die minimalen Begründungsanforderungen von <ref-law> erfüllt. Strengere Anforderungen gelten, wenn die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung - <ref-ruling> E. 1.4.3 S. 255) geltend gemacht wird. Dies prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Pauschale Verweisungen auf Rechtsschriften in den vorangehenden Verfahren genügen diesen Begründungsanforderungen nicht (<ref-ruling> E. 1.3 S. 306).
Soweit der Beschwerdeführer vorliegend die Anwendung des kantonalen (u.a. auch Verfassungs-) Rechts kritisiert, sind der Beschwerdeschrift - in welcher darüber hinaus pauschale Verweisungen enthalten sind - kaum taugliche Rügen zu entnehmen. Es kann allerdings dahingestellt bleiben, inwieweit der Beschwerdeführer die eben genannten Begründungsanforderungen erfüllt, da seine Beschwerde ohnehin abzuweisen ist:
2.
2.1. Das Obergericht hat unter Hinweis auf Lehre und Rechtsprechung zum Verfügungsbegriff (vgl. auf Bundesebene statt vieler etwa <ref-ruling> E. 2.2.1 S. 75) erwogen, blosse Rechnungen seien in der Regel nicht direkt auf Rechtswirkungen gerichtet und besässen nicht Verfügungscharakter, weshalb die provisorische Rechnung vom 5. September 2011 kein taugliches Anfechtungsobjekt darstelle (zumal die Nichtzahlung auch keine Verpflichtung zu Lasten des Beschwerdeführers zur Folge habe).
2.2. Der Beschwerdeführer stellt diese rechtliche Beurteilung an sich nicht in Frage. Er macht aber eine Rechtsverweigerung bzw. -verzögerung geltend, weil die Gemeinde Andermatt bis heute keine anfechtbare Verfügung erlassen habe, obwohl sie im Besitz aller erforderlichen Angaben zur Veranlagung wäre. Er erleide dadurch einen Rechtsnachteil "nur schon mit Hinweis auf die Strafdrohung von Art. 30" des Tourismusreglementes; ausserdem werde die von ihm angestrebte akzessorische Normenkontrolle verunmöglicht. Eine solche solle offensichtlich "um jeden Preis vermieden werden".
2.3. <ref-law> gewährleistet den Anspruch auf Behandlung formgerecht eingereichter Eingaben und verbietet formelle Rechtsverweigerung. Eine solche liegt vor, wenn eine Behörde auf eine entsprechende Eingabe fälschlicherweise nicht eintritt oder eine solche ausdrücklich oder stillschweigend nicht an die Hand nimmt, obwohl sie dazu verpflichtet wäre (vgl. GEROLD STEINMANN, St. Galler BV-Kommentar (2. Auflage 2008), Rz. 10 zu Art. 29). <ref-law> räumt ebenso einen allgemeinen Anspruch auf Beurteilung innert angemessener Frist ein (vgl. <ref-ruling> E. 1.2.2 mit Hinweisen auf weitere Verfassungsbestimmungen mit spezifischen Beschleunigungsgeboten). Was als angemessene Verfahrensdauer betrachtet werden kann, ist im Einzelfall vor dem Hintergrund des Anspruchs auf ein gerechtes Verfahren unter Beachtung der spezifischen Sachverhalts- und Verfahrensverhältnisse zu bestimmen. Dabei ist insbesondere auf die Schwierigkeit und Dringlichkeit der Sache sowie auf das Verhalten von Behörden und Parteien abzustellen (<ref-ruling>, nicht publ. E. 2, Urteil 4A_744/2011 vom 12. Juli 2012 E. 11.2).
2.4. Die Gemeinde Andermatt führt in der hier zu beurteilenden Streitsache vernehmlassungsweise aus, der Beschwerdeführer sei mit Blick auf genau diese Streitsache, die bisher nicht habe rechtskräftig abgeschlossen werden können, noch nicht mit einer - die Beherbergungsgebühr betreffenden - definitiven und anfechtbaren Veranlagungsverfügung bedient worden. Damit liegt weder eine Rechtsverweigerung noch eine Rechtsverzögerung vor: Die zuständige Behörde hat sich keineswegs verweigert, sondern sich im Gegenteil mehrfach bereit erklärt, eine förmliche Verfügung zu treffen (vgl. dazu auch das Urteil 2C_244/2007 vom 10. Oktober 2007 E. 4.2). Es erscheint sodann vertretbar, während eines hängigen Verfahrens, in welchem es eben gerade um die Verfügungspflicht einer Verwaltungsbehörde geht (vgl. Susanne Genner, Die Verfügungspflicht der Verwaltungsbehörden, Zürich/St. Gallen 2013 S. 72), mit dem Erlass der verbindlichen Verfügung zuzuwarten. Ein Rechtsnachteil entsteht dem Beschwerdeführer dadurch nicht, da er die Rechnung nach der Beurteilung der Vorinstanz noch gar nicht bezahlen muss und sich die Nichtzahlung der provisorischen Rechnung auch strafrechtlich nicht auswirkt (vgl. den Wortlaut von Art. 30 lit. a des Tourismusreglements, wonach mit Busse bestraft wird, wer die "rechtskräftig verfügte" Beherbergungsgebühr nicht oder nicht rechtzeitig bezahlt). Ferner wird der Beschwerdeführer die von ihm angestrebte akzessorische (konkrete) Normenkontrolle im Anschluss an die noch zu ergehende verbindliche Verfügung verlangen können.
Daher bestand für den Beschwerdeführer auch kein Anspruch auf einen separaten Feststellungsentscheid (vgl. dazu ausführlich <ref-ruling> E. 7 S.174, 257 E. 1 S. 259).
3.
Bei diesem Ausgang wird der Beschwerdeführer kostenpflichtig (Art. 65/66 BGG). Parteientschädigungen sind nicht zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird dem Beschwerdeführer, der Einwohnergemeinde Andermatt, dem Regierungsrat des Kantons Uri und dem Obergericht des Kantons Uri, Verwaltungsrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 13. September 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Klopfenstein