I would probably have a CAPTCHA on the form already, to prevent automated signups. Preventing username leakage is a side benefit. An attacker would need to hire a CAPTCHA farm to harvest any significant number of usernames.
If you don't want to use a CAPTCHA for regular signups, you can add one to the page dynamically when you see multiple registrations from the same IP address.
Does this mean that you wait until the user submits the whole login form to display an error message if the username is already taken? Do you display a new captcha for each attempt?
What about sites that let the user know his username is already taken using AJAX? Should this be avoided too?
I like zobzu's idea of using an email as login, though.
If you don't want to use a CAPTCHA for regular signups, you can add one to the page dynamically when you see multiple registrations from the same IP address.