Sachverhalt:
A.
Mit Urteil 8C_373/2010 vom 3. August 2010 wies das Bundesgericht eine Beschwerde in öffentlich-rechtlichen Angelegenheiten des A._ gegen einen Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 15. Oktober 2009 im Bereich des öffentlichen Personalrechts ab und trat auf eine Verfassungsbeschwerde nicht ein.
B.
A._ lässt - unter Hinweis auf das bundesgerichtliche Urteil 6B_383/2018 vom 15. November 2018 - ein Revisionsgesuch einreichen mit dem Rechtsbegehren, es sei das Urteil des Bundesgerichts 8C_373/2010 vom 3. August 2010 in Revision zu ziehen und der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 15. Oktober 2009 sei in Gutheissung der Beschwerde vom 30. April 2010 aufzuheben.
Das Appellationsgericht beantragt die Abweisung des Revisionsgesuchs, soweit darauf eingetreten werden könne. Das Erziehungsdepartement des Kantons Basel-Stadt verzichtet auf eine Vernehmlassung.
Zur Eingabe des Appellationsgerichts nimmt A._ persönlich Stellung. Zudem lässt sich sein Rechtsvertreter dazu vernehmen.

Erwägungen:
1.
1.1. Urteile des Bundesgerichts erwachsen am Tag ihrer Ausfällung in Rechtskraft (<ref-law>). Eine nochmalige Überprüfung der einem Urteil des Bundesgerichts zu Grunde liegenden Streitsache ist grundsätzlich ausgeschlossen. Das Gericht kann auf seine Urteile nur zurückkommen, wenn einer der in den Art. 121 bis 123 BGG abschliessend aufgeführten Revisionsgründe vorliegt (SVR 2014 UV Nr. 22 S. 70, Urteil 8F_14/2013 E. 1.1; Urteil 8F_9/2017 vom 15. Januar 2018 E. 1.1).
1.2. Da es sich bei der Beschwerde in öffentlich-rechtlichen Angelegenheiten um ein reformatorisches Rechtsmittel handelt (<ref-law>), führt dessen Gutheissung oder Abweisung auf der Grundlage der im angefochtenen Entscheid festgestellten Tatsachen dazu, dass der Entscheid des Bundesgerichts an die Stelle des angefochtenen tritt. In solchen Fällen ist das Revisionsbegehren beim Bundesgericht zu stellen, da das Urteil des Bundesgerichts den einzigen in Rechtskraft erwachsenen Entscheid darstellt, der in diesem Zeitpunkt der Revision zugänglich ist (<ref-ruling> E. 2.2 S. 670 f.; Urteil 4F_8/2010 vom 18. April 2011 E. 1.1 mit Hinweisen). Soweit jedoch auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht eingetreten wurde oder ausschliesslich Aspekte aufgegriffen werden, die vor Bundesgericht nicht (mehr) Streitgegenstand bildeten, ist das Revisionsgesuch bei der betreffenden kantonalen Instanz zu stellen (Urteile 4F_11/2013 vom 16. Oktober 2013 E. 3.2.1 und 8C_602/2011 vom 30. September 2011 E. 1.3, je mit Hinweisen).
Da das Bundesgericht die Beschwerde in öffentlich-rechtlichen Angelegenheiten im Verfahren 8C_373/2010 abgewiesen hatte und der Gesuchsteller aus neuen Tatsachen die Ungültigkeit des gesamten ans Bundesgericht weitergezogenen Entscheids des Appellationsgerichts des Kantons Basel-Stadt vom 15. Oktober 2009 ableiten will, ist das Bundesgericht zur Entgegennahme des Revisionsgesuchs zuständig.
1.3. Nach <ref-law> kann die Revision in öffentlich-rechtlichen Angelegenheiten verlangt werden, wenn die ersuchende Partei nachträglich erhebliche Tatsachen erfährt oder entscheidende Beweismittel auffindet, die sie im früheren Verfahren nicht beibringen konnte, unter Ausschluss der Tatsachen und Beweismittel, die erst nach dem Entscheid entstanden sind.
1.4. Das Revisionsgesuch ist gemäss <ref-law> innert 90 Tagen nach der Entdeckung des Revisionsgrundes, frühestens nach Eröffnung der vollständigen Ausfertigung des Entscheids einzureichen.
2.
2.1. Der Gesuchsteller beruft sich auf den Revisionsgrund einer nachträglich entdeckten erheblichen Tatsache gemäss <ref-law>. Er habe durch das Urteil 6B_383/2018 vom 15. November 2018 von der bundesrechtswidrigen Fallzuteilung am Appellationsgericht des Kantons Basel-Stadt erfahren, welche auch bei seinem damaligen, mit Entscheid vom 15. Oktober 2009 abgeschlossenen Beschwerdeverfahren entsprechend ausgeübt worden sei.
2.2. Das Appellationsgericht macht im Wesentlichen geltend, das Revisionsgesuch sei verspätet eingereicht worden. Zum einen hätte der Gesuchsteller bereits im damaligen Verfahren die Spruchkörperbildung des Gerichts in Frage stellen können; zum anderen hätte der anwaltlich vertretene Gesuchsteller spätestens nach der Veröffentlichung des Urteils 1C_187/2017, 1C_327/2017 vom 20. März 2018 Anlass gehabt, die entsprechende Rüge zu erheben.
2.3. Auf die Frage der fristgerechten Einreichung des Revisionsgesuchs braucht indessen nicht näher eingegangen zu werden, da dieses ohnehin abzuweisen ist.
3.
3.1. Zur Konventions- und Verfassungsmässigkeit der Bildung des Spruchkörpers am Appellationsgericht bzw. Strafgericht des Kantons Basel-Stadt sind mehrere Urteile des Bundesgerichts ergangen:
3.1.1. So hat das Bundesgericht im Urteil 1B_491/2016 vom 24. März 2017 dargelegt, gemäss Beschluss der Präsidentenkonferenz vom 20. Oktober 2016 gelte bis zum Erlass des neuen Organisationsreglements die seit Jahrzehnten ausgeübte Praxis weiter, wonach die Erste Gerichtsschreiberin die Spruchkörper zusammensetze. Mangels anderer Vorbringen sei davon auszugehen, dass sie dabei praxisgemäss nach objektiven Kriterien unter Berücksichtigung der Geschäftslast und der Verfügbarkeit der Richter vorgehe. Da ein gewisses Ermessen bei der Zusammenstellung der Richterbank zulässig sei, so das Bundesgericht damals, erweise sich diese übergangsrechtliche und damit nur für einen zeitlich eng begrenzten Zeitraum bis zum anstehenden Erlass eines neuen Organisationsreglements geltende Regelung als konventions- und verfassungskonform (E. 1.3).
3.1.2. Im Rahmen eines abstrakten Normenkontrollverfahrens hat das Bundesgericht im Urteil 1C_187/2017, 1C_327/2017 vom 20. März 2018 (publiziert in ZBl 119/2018 S. 343 sowie EuGRZ 2019 S. 76) sodann entschieden, das Organisationsreglement des Strafgerichts des Kantons Basel-Stadt vom 16. Dezember 2016 erfülle die verfassungsrechtlichen Anforderungen an ein Gericht nicht vollständig, weshalb § 12 aufzuheben sei und das Strafgericht unverzüglich eine Übergangslösung zu finden habe. Zur Begründung führte es im Wesentlichen aus, § 12 des Organisationsreglements enthalte hinsichtlich der Zusammensetzung der Richterbank neben einem Hinweis auf die gesetzlichen Vorgaben einzig das Kriterium der Verfügbarkeit der Richter und delegiere die Aufgabe im übrigen vollständig an die Kanzlei A, welche dem Ersten Gerichtsschreiber als Verwaltungschef unterstellt sei. Soweit bei der Zuteilung überhaupt kein Spielraum bestehe, weil sie nach starren Kriterien erfolge, stünden einer solchen Delegation an eine gerichtsinterne, nicht richterliche Instanz keine Bedenken entgegen. Räume dagegen die gesetzliche Normierung - wie in § 12 des Organisationsreglements - Ermessen ein, erscheine es unabdingbar, dessen Ausübung einem Richter als unabhängigem, nicht weisungsgebundenem Organ vorzubehalten. Sowohl einer Gerichtskanzlei als auch einem Gerichtsschreiber fehle diese Unabhängigkeit und sie verfügten auch nicht über demokratische Legitimation. Diesfalls biete eine Gerichtskanzlei nicht hinreichend Gewähr für eine sachliche Handhabung des eingeräumten Ermessens (E. 7 und 8).
3.1.3. Im Urteil 6B_383/2018 vom 15. November 2018 schliesslich hat das Bundesgericht erwogen, die am Appellationsgericht des Kantons Basel-Stadt für die Spruchkörperbildung zuständige Erste Gerichtsschreiberin verfüge in Anbetracht der acht Gerichtspräsidien und vierzehn nebenamtlichen Richterinnen und Richter über ein erhebliches Ermessen. Dies sei mit den verfassungs- und konventionsrechtlichen Vorgaben gemäss dem unter E. 3.1.2 wiedergegebenen Urteil 1C_187/2017, 1C_327/2017 vom 20. März 2018 unvereinbar. Daran ändere nichts, dass die Gerichtsschreiberin im Voraus bestimmte Kriterien wie die zeitliche Verfügbarkeit der Richterinnen und Richter, deren Belastung und fachliche Spezialisierung zu beachten habe. Zu keinem anderen Ergebnis führe auch das unter E. 3.1.1 wiedergegebene Urteil 1B_491/2016 vom 24. März 2017, in welchem das Bundesgericht die übergangsrechtliche Spruchkörperbesetzung am Appellationsgericht durch die Erste Gerichtsschreiberin als verfassungs- und konventionskonform erklärt habe. Die damals vertretene Auffassung lasse sich im Lichte der geänderten Rechtsprechung, namentlich des Urteils 1C_187/2017, 1C_327/2017 vom 20. März 2018, nicht aufrechterhalten. Das Bundesgericht hob den angefochtenen Entscheid auf und wies die Sache zu neuer Beurteilung ans Appellationsgericht zurück (E. 1.2.2 + 2).
3.2. Wie in E. 3.1 hiervor aufgezeigt, hat sich die Rechtsprechung des Bundesgerichts zur Frage der Konventions- und Verfassungskonformität der Spruchkörperbildung am Appellationsgericht des Kantons Basel-Stadt geändert. Die Änderung der Rechtsprechung bildet indes wie auch Verletzungen von Bundesrecht keinen Revisionsgrund im Sinne von <ref-law>. Unter diesem Titel sind nur Tatsachen und Beweise bedeutsam, die im früheren Verfahren vorhanden waren, also nicht neu sind (unechte Noven; ELISABETH ESCHER, Basler Kommentar, Bundesgerichtsgesetz [BGG], 3. Aufl. 2018, N 5 und 7 zu Art. 123; PIERRE FERRARI, Commentaire de la LTF, 2. Aufl. 2014, N. 15 zu <ref-law> mit Hinweis auf <ref-ruling>). Die Geltendmachung echter Noven, das heisst von Tatsachen, die sich erst nach Abschluss des zu revidierenden Urteils zugetragen haben, ist ausgeschlossen (SEILER/VON WERDT/GÜNGERICH/OBERHOLZER, Bundesgerichtsgesetz [BGG], 2. Aufl., Bern 2015, N 7 zu Art. 123). Ohnehin ist der einschlägige Revisionsgrund immer nur dann gegeben, wenn das angefochtene Urteil auf einem falschen oder unvollständigen Sachverhalt beruht, welcher durch die Berücksichtigung nunmehr vorgebrachter Tatsachen oder Beweise korrigiert werden kann, was zu einem andern rechtlichen Ergebnis führt (ESCHER, a.a.O., N 6 zu Art. 123). Eine Rechtsprechungsänderung entspricht hingegen einer rechtlichen Neubewertung. Eine geänderte oder präzisierte Rechtsprechung bildet denn auch regelmässig keinen Grund, revisionsweise auf eine formell rechtskräftige Verwaltungsverfügung zurückzukommen, weil es sich dabei nicht um neue oder geänderte Tatsachen handelt (Urteil 9F_7/2008 vom 9. September 2008 E. 2.2 mit Hinweis auf <ref-ruling> E. 3b S. 131 und 115 V 308 E. 4a/bb S. 313; vgl. auch Urteil 8C_481/2013 vom 7. November 2013 E. 5, nicht publ. in: <ref-ruling>, aber in SVR 2014 UV Nr. 7 S. 21, und Urteil 8C_495/2018 vom 24. Januar 2019 E. 5.5).
3.3. Das Revisionsgesuch ist nach dem Gesagten unbegründet.
4.
Das Verfahren ist kostenpflichtig (<ref-law>). Die Gerichtskosten werden dem unterliegenden Gesuchsteller auferlegt (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Das Revisionsgesuch wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 3000.- werden dem Gesuchsteller auferlegt.
3.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht schriftlich mitgeteilt.
Luzern, 17. Juli 2019
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Maillard
Die Gerichtsschreiberin: Kopp Käch