Very nice, but
should be done otherwise if possible:
- Start building it, cost is cheap
- construction is finished only when you kill, let's say, 100 prisoners in your dungeon - but it can be finished quickly, in a year or less if you meet requirement
- A special execution "skulls for the skull throne" is unlocked, increasing cruel opinion of you temporarily by +1 (but stackable)
- you can give away your own skull as a depressed lunatic
And actually kind of the same thing (with longer natural construction) should take place for epic Cathedrals - they should accumulate enough piety to get upgraded, from priests and societies as well as from ruler and conversion patron. If you can do it, a similar system can be applied to Holy Sites, ability to create new ones and desacrate old ones.