Starting with the supposition that we want to allow humans free agency, insofar as it does not infringe upon the free agency of others, what punishments can a state impose that do not make it guilty of the same infringement?
In other words, is it coherent for a government to punish a person "X" (who took away free agency from another person) by taking away person X's free agency?
In doing so, does this governmental action perpetrate the same offense?
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".
what punishments can a state impose that do not make them guilty of the same thing?
Any punishment which isn't identical to the original crime (except with the guilty party as victim) would count -- then they couldn't technically be held guilty, so they would "not [be] guilty of the same thing." But I'm guessing you're thinking about when the state executes a murderer.
This is a tricky subject, and it's entirely subjective. My sense is that there's not really a contradiction here, just in appearance. That the state can take action in the civil space to protect public safety is entirely reasonable; the question you're asking after (if I'm reading correctly) is the legitimate extension of the states' exercise of power. In particular, if my inference is correct: does it extend as far as destroying human life, even to protect the public?
Of course in practice it does. That doesn't stop the fact that hitting someone for breaking the rule of hitting is hypocritical; but in the case of the state this apparent hypocrisy is mitigated somewhat by their much greater sphere of responsibility, their need to ensure the public of their safety.
In short we have a democracy, that is, the government we deserve. The state executes dangerous citizens and does this because we demand their sacrifice in the name our safety. If we demanded a saner response to criminality and violence we might get one.
what punishments can a state impose that do not make them guilty of the same thing?
None.
It is not coherent for an unrelated third party to enforce the restitution, but the victim or an agent thereof would be justified to claim restitution.
To those that would cry 'anarchy' at this answer, I respond that having the state enforce the restitution is more chaotic than allowing the victim to make him- or herself whole. States do not, and could not, enforce the punishments universally. Further, their laws change constantly at the will of the masses or a despot. That is chaos compared to vigilantism.
1 X's - the criminal's - exercise of free agency may interfere with or hinder the freedom of other agents. If criminal X's imprisonment secures the exercise of freedom of a thousand others, namely X's potential victims, then some exercise of free agency is going to be lost whatever the state does. If it lets X go, X retains the exercise of their free agency but a thousand others lose or are likely to lose theirs. If X is imprisoned, X's loses the exercise of their free agency but the exercise of free agency by 1000 others is secured.
Why should X's free agency take precedence over that of the 1000 ? A critic might reverse the question. In which case I should be obliged to advance considerations of the public interest or the greater good.
2 There is a constellation of values; and free agency is one of them. But it is is not the sole or supreme value, nor if it an inalienable right. Freedom may need to give way to justice; and there would be no free agency without an organised society to secure and protect it. It is reasonable to make respect for others' free agency the social and moral condition for the securing and protection of one's own. Criminal X has not respected the free agency of others, and so can hardly complain if their own free agency is (temporarily) suspended in the nick.
You've answered your own question.
Starting with the supposition that we want to allow humans free agency, insofar as it does not infringe upon the free agency of others
We value free agency, yet the actions of others can infringe upon the free agency of others - in fact, most of the laws that people can break are in place because of some action that infringes upon the free agency of another.
You trespass on someone's property, that's their agency to decide who should and should not be allowed in the privacy of their home. You steal from them, you infringe upon their agency to spend their money as they see fit. You kill them, you infringe upon any decision they will ever make in the future.
With this in mind, we can justify the laws as a necessary measure to prevent people form infringing on others free agency - actions that negatively impact a person's free agency therefore are punished by taking away that person's free agency, scaled for the severity of the infringement that they inflict.
This is a gross simplification, and only takes into account people's free agency as a factor (we value other things, some moreso than free agency, in a society) but based solely on the premises you provided, if we value free agency then we must also punish those who would take free agency away.
