Aviso: não sou especialista em segurança ou neste tipo de ataque.
Cookies e Sessão não resolvem
Cookies e Sessão não são locais adequados para colocar este tipo de segurança.
Cookies são responsabilidade do cliente (geralmente o navegador), portanto facilmente manipuláveis.
A Sessão do usuário, apesar de ficar no servidor, é apenas uma estrutura de dados associada a um identificador, que geralmente fica num Cookie ou então na URL através do URL Rewriting.
Nos dois casos acima, requisições com o intuito de realizar um ataque de força bruta precisam simplesmente simular um novo usuário a cada requisição, como se fosse alguém que tivesse acabado de abrir o navegador, fazendo com que o servidor gere automaticamente uma nova sessão.
Segurança não é só da aplicação
Ataques que envolvem o uso maciço da rede como este ou DoS (Negação de Serviço) geralmente são mais bem tratados por Firewalls ou Proxies que filtram excesso de requisições.
Deixar isso a cargo da aplicação vai trazer uma complexidade para ela e vai fazer a equipe despender tempo implementando algo que não faz parte do escopo do sistema. Essa distração quase sempre vem a custo de um sistema com menos qualidade.
E o IP?
Uma técnica simples, porém ingênua, seria limitar o número de requisições usando o endereço IP.
Isso funciona num ataque simples, oriundo de apenas uma fonte. Entretanto, ataques distribuídos mais sofisticados irão controlar diversas fontes e acaba sendo muito difícil diferenciar uma requisição "normal" de uma automatizada.
Como detectar ataques?
Falando em diferenciar, aí é que está toda a questão. Como detectar o padrão de requisições artificiais geradas pelos ataques das requisições genuínas originadas pelos usuários?
A resposta a esta pergunta faz com que seja possível evitar ataques de força bruta de forma efetiva.
Não tentarei responder isso aqui, já que será assunto de debate por especialistas em segurança.
Até consigo pensar em pequenas técnicas para dificultar a ação de um hacker, mas em última análise, sempre será possível que ele identifique essas técnicas e ajuste o ataque.
Talvez usar um captcha ou "teste de humano" equivalente seja uma das formas mais efetivas hoje, porém muitas vezes atrapalha a usabilidade e também há garantias de que não possa ser implementado um algoritmo automatizado que resolva esses desafios.
Considerações
O objetivo desta resposta é informar aos desenvolvedores de aplicações web para não tentar reinventar a segurança usando técnicas "ingênuas". Ao mesmo tempo, quero dizer que a segurança deve ser uma preocupação, mas exige um estudo mais aprofundado, ferramentas adequadas e consulta a especialistas.