First of all, the cost of the belt itself is small (maybe $40-$50) compared to the cost of the labor involved. If you are not going to do the job yourself, let the shop doing the work supply the belt. That way, they will be responsible if anything goes wrong. You don't want to supply the belt and have a problem later on and when you take it back to the shop, they say the belt is the problem and you must pay the labor cost all over again. For a timing belt job, it's just not worth it to supply the part yourself, IMHO.
Second, for $800, they must also being replacing the water pump and all the seals behind the belt and pump.
Third, use this site to check for dealer coupons in your area. Many dealers run specials on timing belt replacement:
http://www.toyotacoupons.com/UI/Deal...lerSearch.aspx
Mike