Time is your friend.
Think about what happens when you draw money from "ye average banking machine".
- User inserts card (read: email/name/whatever),
- Machine says "hi, please enter pincode" (read: password/whatever)
- User can now enter correct pincode within 3 attempts. If that fails, the card is withdrawn and the user will have to wait for the next day to personally apply for a new card and pincode, explaining to his bank what happened.
Now, in your situation you most probably don't want people to come knocking at your door because they failed to enter the correct code. To avoid this, you'll simply have to strip the "come and apply for a new card" thing and what's left is "wait until tomorrow".
So, if you give a user 3 attempts to verify himself/herself and he/she fails... make her wait for an hour before he/she can try again.
If someone would still try to go for a brute force attack, it would enable him to try ("3 attempts per hour" maximum x "24 hours in a day" maximum = 3 x 24 =) 72 attempts a day.
Depending on what he/she is trying to brute-force, 72 attempts a day (which are 26280 attempts in a 365-day year) is wa-ay too slow.
This way - and as long as "reverse engineering" to find a backdoor isn't an option - your "software" should be safe from brute-forcing anything.
A little update, based on the comments to this answer...
Now, what about people getting locked out because one or more malicious people abuse the user name of a specific member and simply try to make sure such a user can't log in because they simply entered a wrong password 3 times?
Right, sounds like a "Denial Of Service"-alike attack. But that won't stop you from doing it this way, as such attacks can be circumvented easy. All you have to do is to make sure you don't forget about a second layer of security for such cases.
Remember that there are things like "security questions". Someone might be able to know or guess your username, but it'll take a truckload of time to get around a security question when locked... unless you know the answer. The security question could be limited to simply "unlock" the "locked" login area.
Think about how Google and Co. do it:
- login with username/email and password,
- fails several times gives a lockout,
- answering security question correctly lifts lockout.
Use a captcha at (1) and (3) to slow down any brute-forcing attempts and you're all set.
If you explicitly do not want to use a captcha (which makes me wonder why), you will have to implement a "user-ip", "time-of-access" checking implementation and slow down access to the system for a random 1 to 2 seconds. This shouldn't be a problem as this would be a similar implementation as the lockout-procedure, only that you don't lockout but slow-down things at certain points so a brute-force attack takes time. A 1 second slowdown on 1 page will limit brute-forcing to 60 attempts per minute, while you're locking out the brute-forcer after 3 failed attempts. Same goes for the security question: slow it down. The brute-forcer will have to be smart enough to deal with both points and will have to brute-force both of them at the same time... stealing his valuable resources and time to cause havoc.
However you do it. If you do it like this, there's no need for the admin to even leave the coffee machine while all that's going on, and it solves any problems you think you might have discovered relating to "locking out legit users with a DOS-alike attack".
Let's look at the initial example I provided above in (3):
If that fails, the card is withdrawn and the user will have to wait for the next day to personally apply for a new card and pincode, explaining to his bank what happened.
Well, the "security question" option to enable legit users from lifting the lockout is just like being forced to personally visit and talk to your bank. Just easier.
Also, this "unlocking" procedure can be useful for the admin/sysop as a simple log file showing the number of "attempts" can help the admin to track down attempts of a definitive attack. Any script kid could try to lock out users by entering the wrong password 3 times... but if someone fails answering the security question severaltimes, there's something bad going.
And last but not least: just like an onion, such security layers can even be wrapped into each other (if it makes sense, like in high-security environments).
The simple trick is to make it hard for people to mess with things, while keeping the regular user happy.
I can only repeat: time is your friend... (the rest is simple logic)