government is used flexibly, so whether you can have a state without one is dependent on which definition you're using. both government and state are used in the overarching way that you're talking about, as the fundamental thing that anarchists are fighting against, and both are also used for specific bodies or specific institutions.
proof that this is an ongoing issue...
malatesta (in "anarchy") said:
"Anarchists, including this writer have used the word State, and still do, to mean the sum total of the political, legislative, judiciary, military and financial institutions through which the management of their own affairs, the control over their personal behaviour, the responsibility for their personal safety, are taken away from the people and entrusted to others who, by usurpation or delegation, are vested with the powers to make the laws for everything and everybody, and oblige the people to observe them, if need be, by the use of collective force.
In this sense the word State means government, or to put it another way, it is the impersonal abstract expression of that state of affairs personified by government....
...
For these reasons we believe it would be better to use expressions such as abolition of the State as little as possible, substituting for it the clearer and more concrete term abolition of government."
he also defines government as:
...a series of institutions (legislative, judicial, military, political, and financial) which impose, through collective force, a social order on the people.
but the point is that the state includes a government (or governments), but is not limited to them, it is also the *context for* the government.
at least, that's how i use it, in line i think with weber's definition...
the state is the only legitimate authority using power (within certain territorial boundaries) and the authority that gives legitimacy to institutions to use compulsory means (punishment, laws, police, etc.)