Sachverhalt:
A.
A.a. M._, geboren 1964, war seit 1. Mai 2002 als Gemeindeverwalter in der Gemeinde X._ angestellt. Mit Verfügung vom 5. Dezember 2005 löste der Gemeinderat das Arbeitsverhältnis fristlos auf. Nach Überweisung an das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht (nachfolgend: Appellationsgericht) des dagegen erhobenen Rekurses an den Regierungsrat hiess das Appellationsgericht den Rekurs teilweise gut, hob die Verfügung vom 5. Dezember 2005 auf und verurteilte die Gemeinde X._ zur Zahlung von neun Monatsgehältern an M._ (Entscheid vom 6. September 2006).
A.b. Mit Schreiben vom 4. Juli 2009 gelangte M._ an den Gemeinderat, um weitere Ansprüche aus dem Arbeitsvertrag geltend zu machen. Nachdem sich die Gemeinde X._ geweigert hatte, eine beschwerdeweise anfechtbare Verfügung zu erlassen, erhob M._ eine Rechtsverweigerungsbeschwerde beim Regierungsrat, welcher mit Präsidialbeschluss vom 13. Januar 2010 darauf nicht eintrat. Den hiegegen erhobenen Rekurs hiess das Appellationsgericht teilweise gut, soweit es darauf eintrat, und wies die Gemeinde an, eine begründete Verfügung zu erlassen (Entscheid vom 22. September 2010).
A.c. Mit Verfügung vom 26. April 2011 lehnte die Gemeinde X._ sämtliche, mit Eingabe vom 4. Juli 2009 erhobenen Forderungen aus dem Arbeitsverhältnis vom 1. Mai 2002 bis 5. Dezember 2005 ab.
B.
Den hiegegen erhobenen Rekurs an den Regierungsrat wurde an das Appellationsgericht überwiesen, welches mit Entscheid vom 29. Juni 2012 den Rekurs abwies.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt M._ Folgendes beantragen:
"1. Das urteilende Gericht habe die vorliegende Beschwerde in öffentlich-rechtlichen Angelegenheiten als reformatorisches Rechtsmittel entgegen zu nehmen, und es habe die Beschwerdegegnerin anzuweisen, dem Beschwerdeführer gemäss § 39 Abs. 2 des baselstädtischen Personalgesetzes (PG, SG 162.100) unter Wahrung des verfassungsmässigen Gehörsanspruch gemäss <ref-law> die bisherige Stelle oder ein neues, der Ausbildung und den Fähigkeiten entsprechendes Aufgabengebiet am bisherigen oder an einem anderen Arbeitsort anzubieten und den Beschwerdeführer rückwirkend auf den 5. Dezember 2005 wiederum bei der Pensionskasse Basel-Stadt zu versichern.
2. Es sei mit Bezug zu den Leistungen der Pensionskasse Basel-Stadt eine Verletzung des Rechtsverweigerungsverbots gemäss <ref-law> und <ref-law> festzustellen.
3. Eventuell: Das urteilende Gericht habe die vorliegende Beschwerde in öffentlich-rechtlichen Angelegenheiten als kassatorisches Rechtsmittel entgegen zu nehmen, und es sei das Urteil des Appellationsgerichts Basel-Stadt vom 6.9.2006 teilweise aufzuheben, das Urteil des Appellationsgerichts Basel-Stadt vom 29.6.2012 vollständig aufzuheben sowie die Sache an die Vorinstanzen bzw. an die Beschwerdegegnerin zur Neubeurteilung zurückzuweisen. Dabei sei im Rahmen der konkreten Normenkontrolle festzustellen, dass § 4 in Verbindung mit 39 Abs. 3 PG Bundesrecht verletze.
4. Es seien die vollständigen Verfahrensakten des laufenden Verfahrens sowie die vollständigen Vorakten des Rekursverfahrens Nr. 2006.604 betreffend die Verfügung vom 5.12.2005, des Willkürbeschwerdeverfahrens Nr. 2007.1007 betreffend Rechtsöffnung in der Betreibung Nr. 7035766, des Klageverfahrens Nr. 2007.170 betreffend Forderung wegen Erschwerung des wirtschaftlichen Fortkommens, des Willkürbeschwerdeverfahrens Nr. 2009.961 betreffend Rechtsöffnung in der Betreibung Nr. 8048256, des Beschwerdeverfahrens Nr. 2010.11 betreffend Rechtsverweigerung und des Beschwerdeverfahrens Nr. 2011.93 betreffend Forderungen aus dem Arbeitsverhältnis beizuziehen und von den Vorinstanzen bzw. der Beschwerdegegnerin zur Verfügung zu stellen.
5. Es sei, falls sich die Darstellung der Eintretensvoraussetzungen wider Erwarten als zu kurz erweisen sollte, dem Beschwerdeführer eine kurze Nachfrist zur Verbesserung seiner Eingabe einzuräumen.
6. Alle ordentlichen und ausserordentlichen Kosten aller Verfahren seien der Beschwerdegegnerin bzw. der Staatskasse zu überbinden. ̈
Die Gemeinde X._ und das Appellationsgericht schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten ist. Die vorinstanzlichen Akten wurden eingeholt.
D.
Unaufgefordert reicht der Beschwerdeführer am 27. Juni 2013 eine weitere Eingabe ein.

Erwägungen:
1.
Der angefochtene Entscheid, ein Endentscheid einer letzten kantonalen Instanz (Art. 86 Abs. 1 lit. d, Art. 90 BGG), betrifft ein öffentlich-rechtliches Arbeitsverhältnis, d.h. eine öffentlich-rechtliche Angelegenheit im Sinne von <ref-law>. Der Ausschlussgrund von <ref-law> ist nicht gegeben, da die Beschwerde Entschädigungsansprüche und somit vermögensrechtliche Angelegenheiten betrifft. Die Streitwertgrenze von Fr. 15'000.- (<ref-law>) ist bei weitem überschritten.
2.
2.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Der vorinstanzliche Entscheid stützt sich in der Sache auf kantonales Recht. Als Beschwerdegrund kommt zur Hauptsache die Verletzung von Bundesrecht, insbesondere von verfassungsmässigen Rechten der Bundesverfassung in Frage (<ref-law>). Die Anwendung des kantonalen Rechts als solches bildet nicht Beschwerdegrund. Überprüft werden kann insoweit nur, ob der angefochtene Entscheid auf willkürlicher Gesetzesanwendung beruht oder ob das Gesetz oder seine Anwendung sonst wie gegen übergeordnetes Recht verstossen (vgl. <ref-ruling> E. 1.2.1 S. 251 f.). Hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht gilt eine qualifizierte Rügepflicht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.1 S. 53). Wird eine Verletzung des Willkürverbots geltend gemacht, muss im Einzelnen dargelegt werden, inwiefern der angefochtene Entscheid an einem qualifizierten und offensichtlichen Mangel leidet. Auf ungenügend begründete Rügen und bloss allgemein gehaltene, appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. 1.3 S. 262; <ref-ruling> E. 2.1 S. 120; je mit Hinweisen).
2.2. Nach <ref-law> legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Abs. 1). Es kann diese Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Abs. 2). Die Voraussetzungen für eine Sachverhaltsrüge nach <ref-law> und für eine Berichtigung des Sachverhalts von Amtes wegen nach <ref-law> stimmen im Wesentlichen überein. Soweit es um die Frage geht, ob der Sachverhalt willkürlich oder unter verfassungswidriger Verletzung einer kantonalen Verfahrensregel ermittelt worden ist, genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Vielmehr ist in der Beschwerdeschrift darzulegen, inwiefern diese Feststellungen willkürlich bzw. unter Verletzung einer verfahrensrechtlichen Verfassungsvorschrift zustande gekommen sind. Andernfalls können Vorbringen mit Bezug auf einen Sachverhalt, der von den Feststellungen im angefochtenen Entscheid abweicht, nicht berücksichtigt werden. Vorbehalten bleiben offensichtliche Sachverhaltsmängel im Sinne von <ref-law>, die geradezu in die Augen springen (<ref-ruling> E. 6.2 S. 288; <ref-ruling> E. 1.4.3 S. 245).
3.
Die Beschwerdegegnerin wiederholt mit Vernehmlassung vom 21. Januar 2013 wie bereits in ihrer Verfügung vom 26. April 2011 mehrfach zum Ausdruck gebracht, dass das Appellationsgericht mit unangefochten gebliebenem Entscheid vom 6. September 2006 über die bei unbegründeter fristloser Auflösung des Arbeitsverhältnisses aus § 39 des Personalgesetzes vom 17. November 1999 des Kantons Basel-Stadt (PG/BS) ableitbaren Ansprüche bereits rechtskräftig entschieden habe.
3.1. Im Urteil 1P.136/1997 vom 8. Januar 1998 E. 3a liess das Bundesgericht offen, ob der Grundsatz ne bis in idem des materiellen eidgenössischen Strafrechts (<ref-ruling> E. 3a S. 264 mit Hinweisen) mit verfassungsrechtlichem Rang (<ref-ruling> E. 2 S. 271 mit Hinweis) auch im Verwaltungsrecht zum Tragen komme. Sinngemäss beruft sich die Beschwerdegegnerin mit ihrem Vorbringen jedoch auch auf das im Verwaltungsrecht unumstrittene Prinzip der materiellen Rechtskraft, wonach ein neues ordentliches Verfahren über einen bestimmten, formell rechtskräftig beurteilten Streitgegenstand nicht mehr zulässig ist, sofern das frühere Urteil nicht mit einem ausserordentlichen Rechtsmittel beseitigt wird (Urteil 1P.136/1997 vom 8. Januar 1998 E. 3a mit Hinweisen). Denn nach Lehre und Rechtsprechung sind Rechtsmittelentscheide unabhängig davon, ob sie von Verwaltungsjustizbehörden oder von Gerichten ausgehen, unter Vorbehalt des Vorliegens von Revisionsgründen prinzipiell unabänderlich (Urteil 1P.136/1997 vom 8. Januar 1998 E. 3c mit Hinweisen; vgl. auch ALFRED KÖLZ/JÜRG BOSSHART/MARTIN RÖHL, Kommentar zum Verwaltungsrechtspflegegesetz des Kantons Zürich, 2. Aufl. 1999, N. 2 f. zu § 66; URS PETER CAVELTI/THOMAS VÖGELI, Verwaltungsgerichtsbarkeit im Kanton St. Gallen: dargestellt an den Verfahren vor dem Verwaltungsgericht, 2. Aufl. 2003, N. 1085 u. 1088). Eine abgeurteilte Sache liegt vor, wenn der streitige Anspruch mit einem schon rechtskräftig beurteilten identisch ist. Dies trifft zu, falls der Anspruch dem Gericht aus demselben Rechtsgrund und gestützt auf denselben Sachverhalt erneut zur Beurteilung unterbreitet wird und sich wieder die gleichen Parteien gegenüberstehen (Urteil 4C.204/1995 vom 22. Februar 1996 E. 3b, <ref-ruling> E. 2a S. 90 mit Hinweisen; <ref-ruling> E. 2a S. 743).
3.2. Die materielle Rechtskraft eines früheren Urteils bedeutet grundsätzlich nur eine Bindung an das Dispositiv. Allerdings können zur Feststellung der Tragweite des Dispositivs weitere Umstände, namentlich die Begründung des Urteils, herangezogen werden (BGE <ref-ruling> E. 2a S. 743 mit Hinweisen; <ref-ruling> E. 3b S. 191; <ref-ruling> E. 1 S. 378).
3.3. Mit in Rechtskraft erwachsenem Sachentscheid vom 6. September 2006 entschied das Appellationsgericht, dass der Beschwerdeführer wegen seiner ungerechtfertigten fristlosen Entlassung vom 5. Dezember 2005 gestützt auf § 39 PG/BS Anspruch auf 9 Monatsgehälter habe, der Rekurs jedoch im Übrigen abgewiesen werde, soweit darauf einzutreten sei.
Daran ist das Bundesgericht gebunden. Das in diesem Zusammenhang gestellte kassatorische Rechtsbegehren ist unzulässig (<ref-ruling> E. 1.2 S. 135), weshalb darauf nicht einzutreten ist. Somit steht für das Bundesgericht gestützt auf die Begründung im rechtskräftigen Entscheid vom 6. September 2006 fest, dass an Stelle einer Weiterbeschäftigung eine Entschädigung ausgesprochen wurde und dass das Arbeitsverhältnis auf den 5. Dezember 2005 beendet wurde. Auf das Begehren einer Weiterbeschäftigung ist folglich nicht einzutreten. Das Gleiche gilt für die Forderungen betreffend Zahlungen aus der Pensionskasse ab Beendigung des Arbeitsverhältnisses sowie auf Lohnzahlungen und Ferienentschädigung vom 6. Dezember 2005 bis 11. Oktober 2006, weshalb hierauf ebenfalls nicht einzutreten ist.
4.
4.1. Mit Entscheid vom 29. Juni 2012 schlussfolgerte das Appellationsgericht, dass § 39 Abs. 3 PG/BS die finanziellen Folgen einer unbegründeten fristlosen Entlassung abschliessend regle, weshalb keine Ansprüche auf Ersatz von Verdienstausfall nach <ref-law> geschuldet seien. Die weiteren Forderungen lehnte es ebenfalls ab.
4.2. Gemäss <ref-law> hat der Arbeitnehmer Anspruch auf Ersatz dessen, was er bis zur ordentlichen Beendigung des Arbeitsverhältnisses verdient hätte, was der Beschwerdeführer in diesem Verfahren geltend macht. Neben diesem Lohnersatzanspruch hat der Arbeitnehmer wegen der Rechtswidrigkeit der Kündigung durch den Arbeitgeber einen Anspruch auf Geldstrafe im Sinne von <ref-law>. Diese Geldstrafe soll den Arbeitgeber vor unberechtigten fristlosen Entlassungen abschrecken ( Frank Vischer, Der Arbeitsvertrag, in: Schweizerisches Privatrecht, Bd. VII/4, 3. Aufl. 2005, S. 262; vgl. auch WOLFGANG PORTMANN, Basler Kommentar, 4. Aufl. 2007, N. 5 zu <ref-law>). Mit Entscheid vom 6. September 2006 (E. 4.2) wandte das Appellationsgericht primär § 39 PG/BS an und stellte dabei fest, dass im PG/BS keine Regeln für die Festlegung einer Entschädigung enthalten seien, weshalb in Analogie <ref-law> heranzuziehen sei. Die Frage, ob sich die materielle Rechtskraft des Entscheids des Appellationsgerichts vom 6. September 2006 der damals eingeklagten Entschädigung auch auf <ref-law> erstreckt, kann jedoch offen bleiben. Da keine Identität zwischen dem Lohnersatz- und dem Entschädigungsanspruch besteht, hat die Vorinstanz zu Recht überprüft, inwiefern das OR grundsätzlich Anwendung findet, und dabei - ohne Bundesrecht zu verletzen - zutreffend erkannt, dass § 39 Abs. 3 PG/BS eine abschliessende Regelung vorsieht, weshalb <ref-law> nicht zur Anwendung gelangt. Die Vorinstanz hat sich somit mit dem anwendbaren Recht auseinandergesetzt.
4.3. Der Beschwerdeführer stellt betreffend der Anwendung des OR seine eigene Interpretation des kantonalen Rechts jener der Vorinstanz gegenüber. Inwiefern Letztere krass falsch und damit willkürlich sein soll, legt er nicht klar dar, zumal der Beschwerdeführer in seinen Ausführungen immer wieder davon ausgeht, dass das Arbeitsverhältnis nicht auf den 5. Dezember 2005 beendet wurde. Diese Frage wurde jedoch rechtskräftig mit Entscheid vom 6. September 2006 entschieden (vgl. E. 3 hievor), weshalb auch die Vorinstanz zu Recht von keiner anderen Prämisse ausging. Gleiches gilt bezüglich der Rüge, ihm sei keine Weiterbeschäftigung angeboten worden, dabei ist ihm zusätzlich seine Beschwerdebegründung vom 4. Januar 2006 (S. 23 Ziff. 19.2) entgegenzuhalten, worin er ausdrücklich eine Weiterbeschäftigung ausschloss. Im Übrigen lassen sich § 4 in Verbindung mit § 39 PG/BS ohne weiteres im Sinne der Vorinstanz interpretieren. Sodann kann es nicht als unhaltbar bezeichnet werden, wenn gemäss kantonalem Gericht mit § 39 Abs. 3 PG/BS sämtliche Entschädigungen wegen unbegründeter fristloser Kündigung abgegolten wurden, zumal eine entsprechende Entschädigung bis zu zwei Jahresgehältern betragen kann. Betreffend der Höhe der Entschädigung ist auf Erwägung Ziff. 3 hievor zu verweisen, weshalb das Bundesgericht an die festgelegte Höhe gebunden ist. Der Standpunkt des kantonalen Gerichts, wonach § 39 PG/BS ohne Ausdehnung auf <ref-law> anzuwenden ist, verletzt demnach weder das Willkürverbot noch anderes Bundesrecht.
4.4. Nicht als substanziiert betrachtet werden muss die Rüge, die Vorinstanz habe bezüglich Ferienentschädigung, Überstunden und Übernahme der Weiterbildungskosten eine willkürliche Beweiswürdigung vorgenommen. Entgegen den Ausführungen des Beschwerdeführers hielt das Appellationsgericht zu Recht fest, dass die dargelegten Beweisofferten nicht taugen. Sodann obliegt es dem Beschwerdeführer, die geltend gemachten Ansprüche zu beweisen (<ref-law>). Inwiefern in Zusammenhang mit der geltend gemachten Vergütung von Überstunden das Appellationsgericht zudem das Gleichbehandlungsverbot (<ref-law>) verletzt haben soll, ist nicht ersichtlich. Denn die Vorinstanz geht entgegen den Ausführungen des Beschwerdeführers auf das von ihm zitierte Spesenreglement vom 20. Mai 2003 ein und schlussfolgert zu Recht, dass gemäss Ziff. 6.3 Überstunden grundsätzlich eins zu eins zu kompensieren seien. Betreffend der Kostenübernahme für die Weiterbildung wird vor Bundesgericht nichts vorgebracht, was nicht bereits im kantonalen Entscheid schlüssig und überzeugend entkräftet wurde. Darauf ist zu verweisen. Insgesamt dringen die Rügen einer bundesrechtswidrigen Beweiswürdigung und Verletzung des Gleichbehandlungsgebots nicht durch.
5.
Nach § 40 Abs. 4 des PG/BS, welcher in der Systematik unter Rechtsmittel, Instanzen und Verfahren des Titels Allgemeine Vorschriften figuriert, ist das Verfahren vor allen Rekursinstanzen kostenlos. Die Vorinstanz führte dazu aus, gemäss Praxis des Appellationsgerichts könne bei einem Streitwert über Fr. 30'000.- von dieser Regelung abgesehen werden. Der Beschwerdeführer legt nicht in einer - der qualifizierten Rügepflicht (<ref-law>; <ref-ruling> E. 1.4.2 S. 254 mit Hinweisen) genügenden - Weise dar, inwiefern die vorinstanzliche Kostenerhebung verfassungswidrig sei.
6.
Die Beschwerde ist daher abzuweisen, soweit darauf einzutreten ist. Dem Prozessausgang entsprechend sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Die in ihrem amtlichen Wirkungskreis obsiegende Beschwerdegegnerin hat keinen Anspruch auf Parteientschädigung (<ref-law>; Urteil 8C_151/2010 vom 31. August 2010 E. 6.1).

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 Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Luzern, 3. Juli 2013
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Leuzinger
Der Gerichtsschreiber: Hochuli