Die genaue Lösung fand sich schließlich in dieser Anleitung zum Debranden von Mobiltelefonen. Es gibt Versionen der Nokia-Firmware, die andere Kombinationen von Sprachen (und somit auch Schriften) unterstützen, ich musste also eine andere Firmware als die vorinstallierte dazu installieren. Das ging zum Glück recht einfach, zumal sich ja das 6300 auch mit einem ganz normalen Mini-USB-Kabel mit dem PC verbinden läßt. Ich folgte im wesentlichen dieser Anleitung, d.h. ich installierte mir zunächst die NSS (Nemesis Service Suite) Software, danach die aktuelle Nokia Software Updater Anwendung (leider ist zu beidem Windows notwendig).
Das Vorgehen besteht vor allem darin, zunächst den Produkt-Code im Handy auf die Version zu setzen, die der gewünschten Firmware entspricht, dazu ist die NSS-Software notwendig. Für mich war der Code 0543123 (EURO-I, Latin, blksilver) der richtige, mein Handy hat nun immer noch deutsche Menu-Führung, aber die Eingabesprachen für SMS sind nun Englisch, Deutsch, Russisch, Bulgarisch, Rumänisch und Ukrainisch.
Die ganze Sache verlief völlig problemlos, interessanterweise überlebten sogar die von meinem Mobilfunk-Provider gesetzten Einstellunge (SMS-Center etc.) die Prozedur, ob andere Daten geschrottet wurden, kann ich nicht sagen, da mein Handy fabrikneu war.