The explicit purpose of a state is to inhibit agency. A state is the opposite of anarchy - anarchy is the scenario where all individuals have absolute agency over themselves and their environment, which is often detrimental to most if not all of those individuals. As such, the very nature of the state is an entity which limits ones agency in exchange for similarly limiting the agency of others. Therefore to seek a state which does not infringe on the agency of its citizens is somewhat contradictory.
There are very few, if any, things a state does which do not constitute an infringement on agency. You must pay taxes, you must pull over or get out of the way when you see flashing lights on the highway - you must follow the highway at all, you must respect other's property rights and you must not lie under oath, just to name a few. These are fundamental functions of the state, to propose a state lacking these (sort of) functions is to propose nothing at all.
As such, it isn't useful to compare the actions of the state to the actions of individuals. It is perfectly alright for the state to mandate you get out of the way when emergency vehicles need to get through on the highway, for instance. It would be counterproductive, not to mention silly and inefficient, if anyone could do that whenever they pleased.
And so, to address your question, as it is a necessary part of the state's role to infringe on agency, it seems highly unlikely to me that there is any way for the state to properly punish those who inhibit others' agency without in turn limiting the criminal's agency.
Not to mention that the very word punishment could be defined as "infringing on another individual's agency in response to a previous action on their part", which would render your question the paradoxical "how can the state infringe on individuals' agency without infringing on their agency?"
A related question that perhaps could be explored further might be "When is it wrong for the state to infringe on the agency of its citizens?" and this question has been, at least to American standards, been answered by The Deceleration of Independence, The US Constitution, and the Bill of Rights. This question is, I think, the fundamental underlying question of any state which professes a duty to its citizens - that is to say any state which agrees with your "supposition that we want to allow humans Agency".