I'm reading Stirner's The Ego and Its Own and I'm struck by how modern some of the ideas he's presenting are. In particular, he defines the state as the group of people with the autority to do violence to members of a community. Is he the first person to say this? If not, who said it earlier?
In political science, the person who defined (rather postulated) the nation state as the territorial monopoly on violence is attributed to Max Weber. Weber's own precise expression is "the monopoly of the legitimate use of physical force within a given territory” (in his Politics as a Vocation). By legitimate, Weber means the successful execution of power monopolization to the effect that the monopolizing entity has the military force, and the people within the territory acknowledge only this entity's having the power and obey its commands. That is, as a sociologist, Weber did not attach any normative value to legitimacy. Under this interpretation, there is no moral difference between the nation state and mafia. The intellectual tendency in political science and sociology (e.g., Mancur Olson in Power and Prosperity) in fact is that the origin of the nation state is the last mafia standing. That is, the one that was able to eliminate all other competing mafias and to create a stable method of succession became the essential constituent of the government. It is political philosophers who have attributed normative value to legitimacy.
Based on this background in academia, Max Weber should be the guy you are looking for. There are two problems however. One is that Weber's definition comes after the publication of Stirner's The Ego and Its Own, which was published in 1844: Weber's was published in 1918. A way to solve this problem is to indicate that it is the historical common sense that only the state has the right to violence. That is, even peoples in antiquity understood the violent yet justified power of the government (e.g., who killed Socrates?) If any entity grasps a person with force and puts the person in a tiny room without the person's consent, we call it kidnapping; if the government does the same thing, it is called retributive justice.
Second, your phrase of "the state should hold monopoly on violence" is incorrect in that no scholars meant monopolization of violence prescriptively. They meant it as a descriptive, defining idea of a nation state, as "the state holds monopoly on violence.
I know the question is old but for anyone who happens upon this later, Weber attributed the observation to Trotsky at the Brest-Litovsk negotiations of 1918. Trotsky in turn attributed the observation to Lenin. The closest thing I've found to the monopoly idea in Lenin's published works is:
“At the decisive moment in the decisive point one must deploy the overwhelming superiority of forces--this ‘law’ of military success is also a law of political success, especially in that bitter, seething class war, which is called revolution.”
Vybory v uchreditel’noe sobranie i diktatura proletariata:The translation is my own.