Preventing Brute Force Logins on Websites

In my eyes there are several possibilities, each having cons and pros:

Forcing secure passwords

• Pro: Will prevent dictionary attacks
• Con: Will also prevent popularity, since most users are not able to remember complex passwords, even if you explain to them, how to easy remember them. For example by remembering sentences: "I bought 1 Apple for 5 Cent in the Mall" leads to "Ib1Af5CitM".

Lockouts after several attempts

• Pro: Will slow down automated tests
• Con: It's easy to lock out users for third parties
• Con: Making them persistent in a database can result in a lot of write processes in such huge services as Twitter or comparables.

Captchas

• Pro: They prevent automated testing
• Con: They are consuming computing time
• Con: Will "slow down" the user experience
• HUGE CON: They are NOT barrier-free

Simple knowledge checks

• Pro: Will prevent automated testing
• Con: "Simple" is in the eye of the beholder.
• Con: Will "slow down" the user experience

Different login and username

• Pro: This is one technic, that is hardly seen, but in my eyes a pretty good start to prevent brute force attacks.
• Con: Depends on the users choice of the two names.

Use whole sentences as passwords

• Pro: Increases the size of the searchable space of possibilities.
• Pro: Are easier to remember for most users.
• Con: Depend on the users choice.

As you can see, the "good" solutions all depend on the users choice, which again reveals the user as the weakest element of the chain.

Any other suggestions?

I think database-persisted short lockout period for the given account (1-5 minutes) is the only way to handle this. Each userid in your database contains a timeOfLastFailedLogin and numberOfFailedAttempts. When numbeOfFailedAttempts > X you lockout for some minutes.

This means you're locking the userid in question for some time, but not permanently. It also means you're updating the database for each login attempt (unless it is locked, of course), which may be causing other problems.

There is at least one whole country is NAT'ed in asia, so IP's cannot be used for anything.

You could do what Google does. Which is after a certain number of trys they have a captacha show up. Than after a couple of times with the captacha you lock them out for a couple of minutes.