Namely, it provides for a convenient Schelling point for national leaders

The Schelling Point is stronger for monarchs than for ministers, and so as monarchies disappear or become less relevant one could expect assassinations to increase.

But more importantly, who are all these heads of state supposedly assassinated under orders from rival governments prior to 1939?

Does the first such assassination have to be a surprise? I think unprecedented events can be unsurprising if they were anticipated. We may be interpreting Wittgenstein's comment very differently: for me, "X would not surprise me" means something like P(X)>.01, not something like P(X)>.5.

But, since you asked, consider the case of Tomas Mac Curtain, assassinated by British forces in 1920. I don't think he qualifies as a head of state, but he was a fairly prominent government official. In 1939, it would have been plausible that Napoleon had been poisoned by the British (though that's a bit outside your hundred year window).

do you think that it was possible for a non-biased observer in 1939 to view the accusation against British government plot to assassinate the German head of state as unsurprising?

I don't think this is the question you meant to ask, but I think that the accusation should have been entirely unsurprising, regardless of its veracity. I think that most observers would assign a higher probability to the accusation being false than true, but I don't think an unbiased, moderately informed observer could put the chance that the accusation was false at less than ~5% on the day the accusation was reported.