I don't really like this... Thats not very historic. Look at all the independent states of the Rus. No one of them make itself to a kingdom. Also not one of the many historical Italian states etc.
I would like to see a "fear factor" in executions. If I have that one vassal who is always giving me problems and even rebelling, I should be able to execute him to set an example to my other vassals. Yeah, it should have a relations penalty, but it should also have a factor of reducing the chances that other vassals will rebel.