One possibility is to consider using client puzzles. The basic idea is to force the client to do a significant amount of work, and prove it has done so, before you will accept a username/password pair and try to validate it.
Here is an overview of the approach. The server generates a random puzzle, and sends the puzzle to the client. The server generates the puzzle in a way that it can predict reasonably well how much effort will be required to solve the puzzle (e.g., 100ms of computation). The client solves the puzzle, and then sends the solution along with the user's username and password.
This makes it harder for an attacker to DOS the server. For instance, if it takes the server 100ms of computation to check the validity of the user's password, and if the server chooses a puzzle that takes 100ms to solve, then an attacker will have to do at least as much work as the server. If you turn up the dial to select puzzles that will take 200ms to solve, then now the attacker has to do twice as much work as you, to DOS you. Thus, this does not prevent DOS, but it makes it harder and requires the attacker to invest more resources -- which may reduce the risk somewhat.
Here's a very simple example of how to construct a puzzle. The description of the puzzle is a random 128-bit number R (chosen by the server, and sent to the client). The goal is to find a number n such that SHA256(R, n) is zero in its low 20 bits. The client can loop over values of n (test whether n=0 is a solution, test whether n=1 is a solution, test whether n=2 is a solution, ...) until the client finds a solution. On average, you should expect this to take about 220 trials. If the client can perform about ten million hashes per second, then 220 trials should take about one-tenth of a second (100ms). Once the client finds a solution, the client can send n to the server. Note that the server can quickly verify that n is a valid solution to the puzzle (it takes only one hash, not a million hashes). This creates the required assymetry, where the server can very quickly generate new puzzles and verify claimed puzzle solutions, but where it takes longer to solve the puzzle, and where the server can control how long puzzle-solving takes with a fair degree of accuracy. This is just one example of a puzzle construction; there has been a great deal of research on this problem, and there are better constructions.
You might be especially interested in kaPoW, which implements this idea for the web context.
The main limitation is that this is not going to be secure against dedicated attack. A serious attacker can just acquire a botnet of a few hundred machines (this is not that expensive) and DOS you, and now you're completely hosed. Client puzzles can't stop that kind of attack: they can only stop a relatively low-grade attack. However, stopping DOS is in general very difficult.
A variant of this idea is for the server to monitor itself and check whether it is under heavy load. Under normal conditions, skip the puzzle. However, if the server seems to be under DOS attack, then start requiring login attempts to come with a puzzle solution. This mitigates some of the disadvantages of the client puzzle approach, but still is far from perfect, and still cannot withstand a serious DOS attack.
I describe this potential solution, in case you interested, but I don't really recommend it for most sites. For most sites, the risk of DOS is relatively low, and if it does occur, you can deal with it at the time. For that reason, my guess is that it probably isn't worth your time or energy to implement these kinds of defenses. If you've got that much extra time and energy to spare, you might be better off spending it building new features or making your site better.