Rebuilds cost $1000-1500 depending one where you go and the condition of the hard parts of your tranny.
To answer your main question about what you should do, you want to contact Ed Morad and get a low-mileage 4t65e transmission from a similar year car. This is the answer to what you are asking.
A new transmission is roughly the same cost as a rebuild but the rebuild does nothing more than replace clutches and bands. A new, low-milage tranny means all the hard parts, bands, and clutches have little wear.
I don't think there's any way (besides stupidity) that your 3.1 could frag a tranny. It takes a fair amount of power (not a whole lot though) to really start breaking stuff in them.
I'm running 13s on a non-HD 4t65e with 130k miles. I had a rebuild around 117k iirc.