Solution:
Yes, you have to have cookies enabled in order to login to WordPress. Note that the front-end of your site should work fine without cookies, so long as you haven’t incorporated any features that rely on cookies.
I don’t think you’re going to have much of an issue with people needing to enabled cookies, because the vast majority of people would not have disabled them in the first place. Anyone who has disabled cookies is going to have issues with a lot of sites, not just yours. It’s likely that they will know how to enable cookies because, 1) they disabled them in the first place and 2) they will probably have done it for other sites.
That said, there is at least one way you could accomplish a cookie-less login, but WordPress does not support this approach out of the box. See:
PHP session without cookies
WordPress does not use PHP sessions by default, but with a bit of work you could override the default authentication handling and use a cookie-less session. It would take a lot of care to accomplish this without injecting security issues into your site (ex: session hijacking).
My advice is: Just have a cookie!