I found two "good enough" free alternatives:
- StatCounter - this service is free for sites that get up to 9,000 hits per day. Good enough for me. The service provides you all the details you need, including referrals tracking and search engine keywords. The only drawback I found so far - they only keep a log of the last 100 users.
- RE_INVIGORATE Data Archiving Services - this site looks somewhat hackish, because of its design. They offer a totally free service, but it seems limited in comparison with StatCounter.