If you are in position to do so (i.e. not a public API), you can also turn on captcha when under attack. Regular users will be annoyed (or not even that, if invisible) but everything still works for them and you are mostly safe. When not needed, just turn it off again.

You can also allow many more attempts from the known IP addresses for the user, as most users don't change their IP too much. Still, some do, but they will probably authenticate correctly within one or max. two requests.