When Weber is talking about the state being defined by a monopoly on violence, he’s talking about the definition of the modern state as opposed to the pre-modern, not an inherent feature of all human organization and government. The medieval king, for example, certainly didn’t hold a monopoly on violence.
He did indirectly, through the concept of divine right. This power was so immense, that a single king could wage war against an entire religion, as in the Crusades. If that isn't monopoly on violence, I don't know what is.
Anyway, not sure what you’re arguing against: the divine right of kings is exactly the kind of thing I’m talking about when I say legitimacy.
We hear something like “the state is a monopoly on violence” very frequently, but without the idea’s original limited context as part of the definition of the modern state. It helps it go unexamined that our personal experience is only with modern states, so it seems intuitively fundamental. We take it to mean that the legitimacy of the state derives from the power of the army (and police, etc). It feels like hard-eyed realism, seeing through the masks to the coercion beneath. But the real situation is reversed, and historically governments without a strong enough story of legitimacy are unable to create or sustain a monopoly on violence. (Note that violence may be an important part of that story, as with the American revolution).
To go back to Rome as an example of how this kind of “realism” can fail us, power in the republic being reduced to who could muster the most swords or the biggest mob wasn’t the true nature of government revealed, it was the end of the republic.
I’ve written way more than I intended, but I really enjoy talking about this stuff. I’m not saying that the monopoly on violence line is wrong exactly, but that taken too simply it can be misleading.
(I’m aware that the Rome example is fraught—after all it isn’t a modern state so we shouldn’t apply Weber’s terms. But for this purpose I think it works: it’s arguably the closest thing to a modern state in the pre-modern western world, and goes to my point about how power and authority are more complex than a “realistic” view that reduces it to violence.