Besides instant brain destruction, what would it take to kill Tatsuya? Tatsuya can cast Regrowth on himself as an instinctive and reflexive measure. He did it twice in the anime (the first time when he tuned his sister Miyuki's CAD and enraged the brocon girl by not gawking at her semi-nude body, the second time when he received a lethal blast during the Monolith Code final at the Nine Schools Competition).

The wiki states (probably sourced from the novel) that his Regrowth was fast enough to be imperceptible to everyone watching the match, including Retsu Kudou, the patriarch of the 10 clans (who is probably the most perceptive and experienced magician of Japan, and the guy that could see with bare-eyed the Chinese virus Golden Electron Silkworms injected into Miyuki's CAD).

The time required to cast Regrowth into another subject using his Taurus Silver CAD (confirmed by Miyuki during the third arc) is 0.2 seconds.

Instantaneous brain destruction (like a nuclear blast primary zone, or dipping the head in lava, etc), should be enough to kill him because his magical processor would go down with it.

What else could kill him?
What this comes down to is essentially the following:
Aside from instant brain destruction you mentioned, or instant entire-body destruction (which is essentially the same thing), Tatsuya can repair whatever damage has been dealt to him and survive.



The only sure way to take him down is to hit him with something that there's definitely no recovery from, such as Ichijou Masaki's Rupture. An attack like this would all but annihilate the body (including the brain, and therefore magic calculation area), meaning Tatsuya would certainly die. However, this is far easier said than done, as we know he is especially skilled at using counter-magic derived from his Decomposition ability.

Having said that, he isn't impervious to assault - he's struck by a sniper's bullet in episode 19 of the anime, and is overwhelmed by Masaki's uncontrolled Air Bullet (albeit while being under limitations) in the Monolith Code final, meaning it is potentially possible to land a lethal attack. And if the right kind of attack does hit, he's just as mortal as the next guy.



Tatsuya's Regrowth can heal major and minor wounds alike in a fraction of a second, meaning that he can maintain combat effectiveness through almost any injury he sustains. Lacerations, broken bones, and even the removal of one of his arms can be repaired without diverting his full magic calculation area to the matter at hand:


  "A thin ray of light was squeezed out and grazed Tatsuya’s right arm.
  
  Despite it only being grazed - Tatsuya’s right arm from the elbow down was carbonized and blown away.
  
  [...]
  
  Into that gun barrel, Tatsuya thrust his gun shaped CAD, the custom Silver Horn, Trident.
  With the right arm that was supposed to be blown away.
  
  “That arm!?” Lina shrieked."
  
  Volume 11 - Visitor III, Chapter 13


He does, however, reflexively heal any would-be fatal wounds that occur - and that can be exploited:
When used intentionally, as in the above quote, Tatsuya can control the magic he's wielding. When used reflexively on major wounds, that control is lost and the casting of Regrowth uses his entire magic calculation area, meaning he's left in a vulnerable state during the regeneration process. While only a short period, during this time he's completely open to attacks. Those mentioned in the first half of the answer would have no resistance, and even conventional attacks that strike the brain would be enough to kill him.

This essentially amounts to the point that Tatsuya has only two major weak spots - his brain, and his heart. This is proven during his fight with the Parasite Dolls in volume 12, where he only focuses on protecting those two points from any attacks.


  "Amid the incoming superpower [...] attacks coming from all directions, Tatsuya charged forward while only protecting the vital areas of the head and heart and swiftly came into contact with the first Parasite doll.
  
  [...]
  
  Utilizing a full backup of Restoration could block the pain, but under those circumstances, Restoration would temporarily monopolize the entire Magic Calculation Area, crucially delaying any counterattack.
  
  It was precisely for this reason why Tatsuya shielded the vitals that impacted life and death. So long as his Psions were not exhausted, he wouldn’t die even if suffered a fatal injury. However, if he did suffer a life threatening blow, then his survival instincts would automatically initiate a full backup and put every other magic ability on hold.
  
  Volume 13 - Steeplechase, Chapter 7


If you can destroy the brain, that's enough to put him out permanently. If you can severely damage his heart, that would force him into automatic regeneration and therefore potentially provide enough of an opening to perform the first action.



The only other way to take down Tatsuya is mentioned briefly in that previous quote:


  "So long as his Psions were not exhausted, he wouldn’t die even if suffered a fatal injury."


As all magic requires Psions to cast, if his supply was empty, he would be unable to restore himself, reflexively or otherwise. Therefore, if it was possible to completely drain Tatsuya's supply of Psions, a fatal wound (even one not targeting the brain) would be enough to kill him.

Of course, this is practically nearly impossible, as he has such a huge Psion count - even Mayumi Saegusa comments on this after he uses Gram Demolition during the Nine Schools Competition:


  "But there are very few people capable of performing this feat. I cannot do it either. Since this isn't an interference ability but a true dispersion, I am unable to create that kind of force with my psion count.
  
  In summation, it's a super heavyweight!
  
  [...]
  
  There were at least ten overlapping Magic Sequences during the incident, but they were all dispelled instantly... Exactly how
  high is his psion count..?"
  
  Volume 4 - Nine Schools Competition II, Chapter 10




If nothing else, you could always wait for him to die from old age. While he can repair any injury, he still ages, and will therefore die like anyone else after so long.