You could rate-limit at a higher limit based on username as well.
I guess a potential problem with that however is the login-blocking of high profile accounts with known usernames. Maybe only those accounts could be solved by a captcha to bypass the login-block. And if there is a solution like that, login-blocks will basically become useless & therefor also disappear.
> Bypassing an IP block is trivially easy for even a low-sophistication attacker.
Not easy for an average user though.
You're not trying to block the average user, you're trying to block the people trying to abuse the system.
Rate limiting and bot blocking are two totally different things. Rate limiting only increases the cost of a bot attack. Either they need more IP's (which are dirt cheap in the black market) or they need more time--either way it is increased cost. But it won't stop a bot. Just slow it.
Banning IP's might have worked back in 2000, but these days it is useless. Bypassing an IP block is trivially easy for even a low-sophistication attacker.