Attack vectors for brute-forcing website passwords

How else could a brute-force password attack be carried out?

You've covered both bases, and that's really about it. Either repeatedly submit to whatever web frontend is available, or manage to get a copy of the hashes by cracking the database server, abusing the web software, what have you.

Web frontend cracking is usually more an issue of smart force than brute force, and as a result, it works better than you would assume. For example, given a web site which had a company directory - first, last, and extension - for about 100 people, I was able to "brute force" 30% of the accounts simply by throwing together some algorithmic guesses with that data. And the authentication site was Microsoft Exchange, so I stayed below the threshold of NSA recommended lockouts and was fine. (In fact, this was a pen test and I verified before testing to ensure I wouldn't lock out users, but it was an easy guess to make correctly). Even with the slow rate of guessing, I was done in under a day.

I have seen a fair share of sites that change behavior based on the supplied credentials; submit a username that does not exist and you may possibly get a unique error message or a quicker HTTP response versus submitting a legitimate username/password pair.

One idea - let’s say you successfully steal a valid session of a logged in user and the password change functionality requires you enter in the user’s existing password – you may be able to successfully brute force the password change form without triggering lockouts or captchas to discover the original password.

Gowenfawr already covered user-enumeration (if I understood it correctly).

Most systems (if not all), the lockout policies are for each account. So it should be possible to iterate over all the users you know, trying an amount of passwords that would keep you below the lock-out threshold for each account. And once the grace time for invalid logins have been reached, you try again.

Wouldn't this also be very close to a birthday attack on users password?!

I read an article about a student who did something similar to an online bank. The username was the social security number, and the average bank customer was a male between 30-40 year old. He generated random social security numbers for this age group, and tried different pins (the login was only 4 digit pin code!). I believe he was able to get access to an online bank account for every ~20k attempt.