Well, the definition of 'state' is basically a society with a relatively high degree of task differentiation and specialization (more useful for the early period than Weber's ideal-type of 'monopoly on legitimate violence').
Re state power: early states were highly ritualized institutions, and the king arguably one of the most ritualized figures (often doubling as high-priests), with strict regimes regulating his behavior down to how he was to get dressed. The concept of 'divine kingship' did not (necessarily) mean that kings had unlimited god-like powers, but that their powers were tied to the divine order and thus that their behavior affected crop yield, epidemics, etc. Thus they too had to be scrutinied. Kings still did excercise wide-ranging powers, elites of course benefited, and there were certainly draconian laws pertaining to commoners, but on the other hand the states were much weaker and unstable than their modern counterpart, so the actual assertion of power (as opposed to idealized self-presentation) was also much more precarious, and collapse could turn things on their heads. Bad years for instance often resulted in the delegitimation and overthrow of the king.
We could equally look to the highly rigid family and clan-structures, regulating marriage, food production etc., in many other non-state societies. Historically, families have arguably been more 'totalitarian' in their regulation of individuals than states can ever hope to be.