how to log failed login attempts (bruteforce attack prevention)

I'm currently searching for the best way to prevent my software's webportal from bruteforce attacks and came up with the following idea:

- 3 login attempts without any visual change
- after 3 failed attempts show Google reCaptcha
- allow another 3 attempts but now you have to click the captcha every time
- if the last 3 attempts failed again lock the account

My idea just has major downsides and I hope you could give some advice:

• what happens if the username changes at every login attempt? which account do I lock after 6 attempts?
• how shall I log the 3 failed attempts before showing the captcha?
  • IP? But what if lot's of people from a company network use the software at once?
  • Browser user agent? What if someone who tries the bruteforce attack simply changes the user agent at every login attempt?
  • Cookies?