User enumeration is not so evil. Username is public part, password is secret. For example, on this page we all can know that user James_pic exists on stackexchange. Googling or writing simple crawler can easily give attacker great number of usernames, helping to narrow attack, but other security measures still making attackers task very hard.
Idea is to have security policy (at least unwritten, in mind), separate public and secret things and focus efforts on securing what must be secret. If you want to use username as 'second part of secret', thats probably wrong way, better require two times longer passwords, or two factor authentication, because keeping usernames in secret is much harder.
If for some reason you need to keep usernames secret too (for example, you dont want anyone to know how many users registered) - then maybe better to assign username yourself (e.g. userNNNNN, or user-<10 random letters>) or use apprach with email or phone number as username.