Rebuild is possible, but it also depends on the shape of the transmission and its components. If the case is cracked - sense in rebuilding the tranny. Same goes for if there are a significant amount of damage inside. Stripped gears are one thing - but if they are really bad shape - could be too little left to salvage. Should be able to find a used one from $350 - $800 easy. I've been pricing out 6-speeds for less than $1000 for a project at home. You might find that it is much cheaper to buy a used transmission to swap in there. Even a brand new reman transmission should not set you back more than $1200 or so - many are between $800-$1000. If the mechanic is quoting more than that for just the transmission (labor doesn't count) - then you need to look elsewhere.
First - find out what killed the first tranny. Toyota trannys are not 100% bulletproof, but they are really hard to get to that point, unless someone tried to launch the car hard all the time, powershifted all the time, or sidestepped the clutch. Could be something binding up (motor, transmission mounts, bad axles, CV joints) that can really shorten the life of the tranny. Choice of tranmission lube is also important - as they needed to drained and refilled periodically - more often for more aggressive driving.