I would like to address this question by first asking if brain damage can kill him.
It is important to understand that the series emphasizes a difference between the brain and the mind. There is also a psion body, and a spectral form (which may be the same thing as a psion body), and the idea of life force.
These concepts are related to the mind, and the body, but the author has raised a distinction between them. The exact distinction is unclear, since mind and brain are often used interchangeably. The mind is also called the "soul" at times. For a Western viewer, the soul is probably closer to what this concept represent than the word "mind".
However, A USNA scientist in the visitor arc suggests that the mind is the thinking device, and the brain is simply a communication device.
What seems to be true, however, is that the brain exists in the physical realm, while the mind/spectral body/psion body kind of don't. The latter 3 also in some senses is an existence different from whatever spells are. Tatsuya can only affect spells and the physical realm.
Let me raise some examples of this. Sakurai Honami died because she used up her psions. Tatsuya was not able to heal her because psion exhaustion is not a physical attribute.
When the female vampire/parasite attacked Leo in the visitor arc, she drained Leo's life force; Mikihiko was able to see this by looking at his spectral body.
The pure force of a parasite is a information body, which I assume is something like a mind. Tatsuya cannot affect this with Mist dispersal because it is not a physical thing.
We can conjecture that magic is done with the mind instead of the brain. I am pretty sure we know that Tatsuya can suffer minor brain injury and still regrowth himself. Furthermore, the pure parasite can cast spells.
We can also assume that death occurs with the death of the mind. I offer this conjecture because Tatsuya cannot revive the deads. I believe the reason for this is that he cannot influence the mind. He can create an identical brain, but without the mind, the person is dead, despite being fine physically.
So we have a question of whether or not total brain destruction is enough to kill off Tatsuya. Since we don't know how long the mind can survive without the brain, we are not sure of this answer.
So, what can kill Tatsuya through regrowth? Ignoring his counter magic, basically that falls under 2 categories.
1) Mental Interference Magic/Other things that affects the Mind
The obvious answer here is Miyuki's Cocytus. Miyuki's magic affects the mind, not the brain, which is how she was able to kill the pure form of the parasite. It will freeze his mind, rendering him incapable of casting further magic. Even if he could cast magic, he couldn't restore his mind.
A less obvious answer is Miya's ability to change the mind. She could simply change the structure of the mind to no longer be able to regrowth. Miya's gate could also temporarily shut off Tatsuya's regrowth, allowing any method to kill off Tatsuya. Presumably, possibly with minor variations of the Pledge spell, Miyuki could also seal away his ability to Regrowth.
In any case, any mental attack could either damage/kill off the mind directly, or control the mind to not use Regrowth, allowing conventional means to kill off Tatsuya.
2) Psion Exhaustion/Uninhabitable enivronment
Dropping him in the middle of the sun will kill him. Even if his mind can revive him once, his regrowth cannot maintain his body in the sun. As such, his brain cannot be regenerated, and his mind will eventually die. If that does not happen, psion exhaustion will eventually set in and kill him.
In short, anything which creates a persistent lethal environment will kill him. Furthermore, if you can force him to cast a self restoration in a persistent lethal environment (say, a fire), he will not be able to defend himself. When his body is healed, it will immediately be destroyed again, forcing his self restoration to activate ad infinitum until he dies of psion exhaustion.
A continuous attack after he is forced to use self restoration does the same thing.
2)Put him in a bonfire, or continue shooting him with a machine gun.