Because HTTP is stateless, there's no definite way to know that two hits are coming from exactly the same person (or even the same browser).

As you seem to know quite well, there are standard ways to add session functionalities to http. The client can of course perform a clean request at each time, by cleaning cookies and filtering out session parameters, but the same is true of stateful protocols. It is equally difficult to stop an attacker from performing repeated ftp/ssh/telnet login attempts., so I'd say that the statelessness of http is not the issue here.

HTTP is a stateless protocol, but it allows state via cookies and CGI parameters if both sides cooperate. The server already wants to cooperate, so you just have to provide an incentive to the client.

One way to do this would be to have a cookie that a person using the interface normally would receive, which tracks how many times they've tried to log in and makes them wait progressively longer or whatever else you want to do. The cookie would have to be secured in some way that would make it impossible for the client to just make one up, or to re-use an existing one. You could randomly generate cookie IDs and store them in a database, deleting them when they're used, or use cryptography to make this work (though no crytographic scheme comes immediately to mind).

Once you have a way of generating secure cookies, you can simply check if their cookie is valid, and if they don't present a valid cookie, you penalize them in a way that makes it very difficult to brute-force a password. sleep(30) would be a good penalty.

Something like this is what I'm thinking of (this is perl-like pseudocode):

if (!$login) {
  &print_login_page; exit(0);
}
my($numtries)=check_cookie($cookie);
if ($numtries) {
  $waittime = 5*($numtries-1);
} else {
  $waittime = 30;
}
sleep($waittime);

if (check_pass($login,$password)) {
  welcome(); exit(0);
} else {
  set_cookie(numtries => $numtries+1);
  bad_password(); exit(0);
}
[download]

For several reasons, this is not a good solution to the problem:

First off, you penalize any valid users that want to log in for the first time.

Secondly, any attacker can just start up a bunch of requests at the same time (let's say 10 requests) and still get way more attempts per second. Try to stop that and you'll create a situation where your security system will probably become more convoluted and difficult to test (thus probably still not working correctly).

Anyways I'd go for matsmats++ solution, or go for full client SSL certificates if you can affort the trouble and money.

-- 
#!/usr/bin/perl -w
use strict;$;=
";Jtunsitr pa;ngo;t1h\$e;r. )p.e(r;ls ;h;a;c.k^e;rs 
";$_=$;;do{$..=chop}while(chop);$_=$;;eval$.;
[download]