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.