But invincible, he ain't.
Methods for dealing with the Tarrasque should be divided into two categories: Getting Him Down, and Keeping Him Down.
Getting Him Down
2 - Magic Jar: Classic, timeless, the Magic Jar. It's only a sorcerer/wizard level 5 spell, but it will do the trick. You target the Tarrasque's worst save, and get to possess it! Then, you can either stay a Tarrasque, or suicide with him, moving the Tarrasque and the jar out of range of each other. This method will keep him down too.
3 - Ability Drain: While the Tarrasque is immune to ability damage, he is not immune to ability drain. There is some debate as to whether this is intentional or an oversight, but it is RAW (rules as written). One way to inflict some ability drain is to create some Wraiths or Shadows, through the Oracle's Juju mystery or some other means. Wraiths will deal him d6 con damage, though only if he rolls a one on his fortitude save. Still, the Tarrasque can't do anything about the Wraith hanging around, so it's a good long term strategy. Also, because the Tarrasque won't regain con, he will stop at 0 con and be dead.
4 - Suffocation: The Rules for Regeneration clearly state "Regeneration does not restore hit points lost from starvation, thirst, or suffocation." This means that you can take him out through the spell Suffocation or Mass Suffocation. The bad news? The spell targets his +31 fort save. None the less, it is possible to get him down through these means. The Vacuum is a great example of a build that can pull it off.
5 - Divine Intervention: Divine intervention can seem like a cop out, but it is what a lot of GMs are looking for. Get on the good side with a god, and have him deal with the beast.
6 - Eternal Slumber: At 18th level, the witch character class gains a grand hex of her choice. The eternal slumber hex forces a will save or fall asleep until the death of the witch (wish or similar spells can break it). Since technically the hex is not mind-affecting, the Tarrasque is not immune (though your GM may rule that such a hex is mind-affecting, cuz, well, it probably is).
Keeping Him Down
1 - Constant Damage: Constant Damage is the simplest way to keep the Tarrasque down. There are, of course, a multitude of was to do this. Dumping the Tarrasque in a volcano will do the trick, as will hiring a small army to constantly pummel him. Alternatively, you could open "Joe's Tarrasque Burgers" selling 41 hit points worth of juicy burger every 6 seconds.
2 - Planar Relocation: One method of getting the Tarrasque out of your hair is to take him somewhere far, far away. Plane Shift will do the trick, for a very daring spellcaster. Best of all, the Tarrasque doesn't even need to be dead. Just run up to the baddie, cast Plane Shift (and beat his pitiful +12 Will) and he is outta there! For more fun, take him to the astral plane where he can do no damage. Or take him to a plane where time moves excessively slowly. Or maroon him out in the "Plane-Where-There-is-Nothing-Oh-I-Guess-There-Is-a-Tarrasque-Here-When-Did-That-Happen."
3 - Suffocation or Starvation: The Rules for Regeneration clearly state "Regeneration does not restore hit points lost from starvation, thirst, or suffocation." Thusly, placing the Tarrasque at the bottom of the sea, encased in rock, or in a plane with no food would be enough to get rid of him forever.
4 - Into the Sun: This is really a combination of several strategies, but worth mentioning anyway. At the center of the sun the Tarrasque will take massive damage, be unable to breath or eat, and be squished down to the size of blood cell. After all, the sun is right there.
5 - Harpooned by Immovable Rods: Let's say you build a cage out of immovable rods, or simply use them to harpoon the Tarrasque into the ground. Each immovable rod can hold 8,000 pounds of force. With a strength of 41, the Tarrasque can push at most about 36,000 pounds (max carrying capacity times 5). This means that 5 immovable rods can contain him. To play it safe, grab a couple dozen rods (they are only 5,000 gp a piece) to skewer and restrain him. Technically, immovable rods can be moved with a strength 30 check, meaning the Tarrasque has to roll a 15 or better. However, it is perfectly reasonable (at least in my mind) to assume that being harpooned into the ground and restrained incurs at least a -6 penalty to strength checks, making the roll impossible.
6 - Helm of Opposite Alignment: This method is a bit risky, but can potentially be a huge boon for realm of Good. As the Tarrasque is regenerating (or when he is up, if you can figure out how), plop a Helm of Opposite Alignment onto his head. This will have a 50% chance of making him either Lawful Good or Chaotic Good, and with an intelligence of 3 and wisdom of 15, he should hopefully realize that wanton destruction is wrong and join your party. Worst case scenario, he becomes chaotic or lawful evil, and easier for your friendly neighborhood paladin to smite. Keep in mind that he's only got a 15% chance to fail this will save, so it may take a few tries, but hopefully you are attempting this method when he's already out for the count.
7 - Polar Midnight: The spell Polar Midnight will do the trick. Besides dealing some damage and dexterity damage, the 9th level spell has some particularly nasty effects against creatures that do not move (say, an unconscious Tarrasque). Two rounds in the area of effect, and the Tarrasque's body will be transformed into ice - he can only be saved now by True Resurrection, Miracles, or Wish. The Tarrasque's fort save won't even help him here, and saving against it doesn't prevent this effect. Easy!