That podcast does have an interesting explanation of the idea, and Max Weber did provide interesting insights into it. But the governments exerting monopolistic control over violence (to differing levels at different times and places) goes back basically as far as organised society does. The legitimate claim to violence in self defence is just as ubiquitous and has always been at least philosophically at odds with the claim of the state. With that contention arise from the fact that a claim to violence in self defence must either arise from a failure of the state to perform its duties in upholding law and order, or a failure of the individual to follow the law. With the potential for controversy arising from the fact that it’s largely the state who gets to decide whether it was at fault, or if the individual in question was.
Again, you are excluding the critical phrase legitimate claim, which is at the heart of Weber's definition. That is, the right and legitimacy of that right, is restricted to the state, or an entity acting in the effective capacity of a state, whatever it happens to call itself.
Absent this, one of three conditions exist:
1. There is no monopoly. In which case violence is widespread, and there is no state.
2. There is no legitimacy. In which case violence is capricious.
3. Some non-state power or agent assumes the monopoly on legitimate violence. In which case it becomes, by definition The State.
You might want to consider what a "state" which lacks a monopoly on the legitimate claim to the monopoly on force would look like. To what other entity would it cede that legitimate claim, and/or how would it prevent other entities from enacting capricious violence, as has occurred from time to time in the world, and even now.
The state's claim is to legitimacy. A capricious exercise would be an abrogation of legitimacy
Weber, Max (1978). Roth, Guenther; Wittich, Claus (eds.). Economy and Society. Berkeley: U. California Press. p. 54.
The "monopoly on violence" or "monopoly on force" short-hands are a much more recent emergence, and seem to originate with Murray Rothbard (1960s) and Robert Nozick (1970s), though widespread usage of that phrase really only begins to take off after 1980, per Google's Ngram Viewer: <https://books.google.com/ngrams/graph?content=monopoly+on+vi...>
That shorthand has become quite popular, and is often cited by Libertarians as key to their adopting that particular ideology.[1] As expressed by them the formulation is both incorrect and misleading.
I think you’re really putting the kart before the horse here. It’s certainly not true that no legitimate governments existed prior to the 20th century, regardless of what particular phrases may be been invented to describe them during that time. Just like gravity existed long before Newton managed to come up with a sensible description of it. You also almost get to describing the actual reality of the situation, but not quite, which is that a monopoly on violence and a state are the same thing. All states emerged when some group attempted to assert a monopoly over violence, and whether they fail or succeed in becoming a state comes down to their ability to monopolise violence. The status of legitimacy here is entirely subjective, and if it’s called into question, the only way it’s ever falsified is if some other group successfully challenges that monopoly.