[M4tt0]

OK. Here we go:

(1) The mythtv wiki has a custom modeline for 1360x768@60Hz
(2) The wiki pixel-mapping guide for 1366 x 768 lists my TV as well and seems to reconfirm my initial assumption: They state:
- No pixel-mapping via HDMI
- Possible via VGA
(3) I also found some Intel guy stating that many TVs at the time used "customer" HDMI technology that was not very flexible at the time and could only handle a limited number of resolutions like 720p and 1080i
(4) I simply tested my initial idea and connected the NUC to the TV via the MiniDisplayPort to VGA adapter cable:
- Relaunching Kodi immediately gave me the 1360x768@60Hz mode I was looking for, no way to change to 50Hz though.
- For the first time: No overscan! I get reasonable resolutions on the console and can even see the NUC BIOS on my TV (heyhoo!)
(5) Connected both, the MiniDisplayPort -> VGA adapter and the HDMI out (to split off audio). Again: works! In Kodi I can chose between HDMI1 and DP1 AND I get the sound via HDMI -> HDMI Switch with SPDIF -> old school receiver
(6) With that I could switch back and forth and see the difference:

Clear answer:
- 720p@50 via HDMI looks way better than 1360x768@60 via VGA, especially the colours. Played around with the TV settings a little bit (deactivating all the processing), but no significant improvement. Also limiting the color range in Kodi did not improve the colours.

I will stick with 720p via HDMI now, accept the overscan (no pixel-mapping) and keep the adapter cable plugged in my TV to use it whenever I need to access the BIOS. Need a new TV but will wait until the 4k stuff has settled...