That again would mean that to successfully gain access through a brute force attack he would need to go through all possible usernames combined with all possible passwords, wouldn't it?
Yes, for a true brute force,that's how it works. Which is why brute force attacks are not very effective against systems that have username/passwords that are reasonably random and include numbers and punctuation. However, if you allow "root" to login directly over ssh, then the attacker will know the most important username on the system...root.
That would take a zillion tries and a lot of time, so why are people still bothering to attack my box for ten minutes, going through the alphabetical list once, and then stop?
Exactly. Which is why these attacks are only effective against systems that have very poor passwords, like root/root, admin/admin, etc. Technically most of the attacks you'll see are called 'dictionary attacks' and use a list of words of phrases rather than iterating through letters like "aaaaaa" to "zzzzzz" (really it would be "a" to "zzzzzz").
Can they deduce usernames somehow or are they just plain stupid?
No, they can't deduce usernames (other than "root"), but what they *are* looking for are lazy or stupid administrators who use bad passwords.