I saw that it is possible to sync time from an NTP server over WiFi. I have the HC-06 Bluetooth module and an Android phone that can share its Internet connection with Arduino via Bluetooth. Would it be possible to sync time/date using this infrastructure? And if yes - how (which libraries, etc..)? Has anybody done it already and there is a tutorial on that?
No, not really. It is possible, but not easily like you want it to be. The HC-06 is a Bluetooth-Serial bridge. In the Bluetooth protocol there are many types of interfaces, that a client device might expose to the master. A Bluetooth mouse exposes a HID interface, a headset exposes a corresponding audio interface and the HC-06 exposes a pure Serial interface. Thus the HC-06 does not support what ever interface is used for tethering.
Ways, that may make it possible:
Change the firmware of the HC-06 for exposing the correct interface and interact with it. For this you need to know how to reprogram the HC-06 and how exactly bluetooth works. I guess this is over your current level.
Write an app for your Andriod smartphone, which plays the Serial-Internet bridge on the phone. The app would translate between Serial and Internet, involving your own protocol on the Serial interface. Easiest, when you just make a specialized app for syncing time, so that it does not have to do any other communication.
And at that point it is just too much work to go either way. It is unlikely, that you find libraries or any code for this, since it just doesn't make much sense. Instead you could move from an Arduino to an ESP, which can directly connect to the WiFi network in question and thus get directly the time from the internet, without tethering. That is way easier and you can use the many libraries, that already exist for that problem.