The last thing you want to do is storing all unsuccessful login attempts in a database, that'll work well enough but also makes it extremely trivial for DDOS attacks to bring your database server down.
You are probably using some type of server-side cache on your webserver, memcached or similar. Those are perfect systems to use for keeping track of failed attempts by IP address and/or username. If a certain threshold for failed login attempts is exceeded you can then decide to deactivate the account in the database, but you'll be saving a bunch of reads and writes to your persisted storage for the failed login counters that you don't need to persist.
If you're trying to stop people from brute-forcing authentication, a throttling system like Gumbo suggested probably works best. It will make brute-force attacks uninteresting to the attacker while minimizing impact for legitimate users under normal circumstances or even while an attack is going on. I'd suggest just counting unsuccessful attempts by IP in memcached or similar, and if you ever become the target of an extremely distributed brute-force attack, you can always elect to also start keeping track of attempts per username, assuming that the attackers are actually trying the same username often. As long as the attempt is not extremely distributed, as in still coming from a countable amount of IP addresses, the initial by-IP code should keep attackers out pretty adequately.
The key to preventing issues with visitors from countries with a limited number of IP addresses is to not make your thresholds too strict; if you don't receive multiple attempts in a couple of seconds, you probably don't have much to worry about re. scripted brute-forcing. If you're more concerned with people trying to unravel other user's passwords manually, you can set wider boundaries for subsequent failed login attempts by username.
One other suggestion, that doesn't answer your question but is somewhat related, is to enforce a certain level of password security on your end-users. I wouldn't go overboard with requiring a mixed-case, at least x characters, non-dictionary, etc. etc. password, because you don't want to bug people to much when they haven't even signed up yet, but simply stopping people from using their username as their password should go a very long way to protect your service and users against the most unsophisticated – guess why they call them brute-force ;) – of attacks.