The first option to explore should be to make the service less vulnerable to DoS attacks. The Tor network is small compared to an average botnet and is overloaded. If you design a service to resist attack by a botnet then it already should resist attack by someone using Tor. If your service can't resist attack from a Tor user without blocking Tor nodes then you should be worried about slightly more resourceful attackers
It's hard to give a suggestion of how to harden a site without knowing what resource of the site is the limiting factor. Because Tor is overloaded, I doubt it will be possible to mount a bandwidth DoS of anything except the smallest services. On the other hand, if there is some way to cause the site to do a lot of work by sending a small amount of traffic, then it might be possible to mount a CPU DoS. Cryptographic protocols are frequently a problem in this regard.
If it isn't possible to resist a DoS by being more efficient or by avoiding the more resource hungry cryptographic algorithm options, then it still should be possible to resist a DoS without blocking shared IP addresses like those of Tor exit nodes.
For example, the site could require (pseudonymous) authentication before allowing a user to cause the site to perform an expensive operation. If a DoS is detected then throttling could be done on a per-user basis rather than per IP address. Of course there would need to be some way of preventing the attacker generating lots of accounts, e.g. CAPTCHAs. A downside of this option is that now actions performed under the same user account are linkable, which is harmful for anonymity.
Another option is to have a measure that can be applied to a problematic IP address short of blocking it. If Google detect suspicious behaviour coming from an IP address then future users of the same IP address must answer a CAPTCHA before a request will be processed. If the user answers the CAPTCHA correctly Google will set a cookie which will bypass the CAPTCHA test, at least for a while (so in a way this is like implicitly setting up a temporary account for the user).
Both CAPTCHA tests and requiring authentication are annoying for the user, but at least it is better than blocking IP addresses totally. A longer term solution might be possible based around Nymble or one of its successors where blacklisting of accounts is possible while maintaining the unlinkability of user actions. So far I'm not aware of any deployments of systems like these