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 Art. 29 Abs. 2 BV 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 Art. 9 BV und Art. 29 Abs. 1 BV 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. 