You can’t use session, as it requires the client to store a cookie for you, and an attacker is not going to help you out. You will need some global state.
You needn’t bother tracking IP addresses, as a bad guy will just use an Anonymyzing Proxy.
Don’t use account lock-out unless you have to (PCI requirement), as this just lets the attacker DoS your users.
You also want to avoid DoS-ing yourself by making your server do too much work.
This works:
Upon unsuccessful authentication, store username in global state, along with count. Synchronized count++ if more unsuccessful authentications with that username. I use redis for this.
If count >= threshold, then demand solved CAPTCHA value before proceeding. Show CAPTCHA on login screen.
Upon successful authentication, clear stored username in global state. Give user “trusted user agent” HMAC’d cookie, so they don’t have to CAPTCHA in the future for that username on that UA.
You can do the same for passwords, but probably with a higher threshold.
If you don’t like CAPTCHA then demand Proof of Work, for example by making the client calculate and submit the prime factors of a very large number.
While you’re at it, make sure you are using bcrypt to hash your passwords, and that the cost factor is high enough that it takes >= 250ms to hash a password. This slows down your server but also slows down an attacker. Avoid hashing unless they pass the CAPTCHA (if required).
Encourage users to use long, complicated, memorable? passwords, so that they’re harder to brute-force.