Sounds like you might have (partially) answered your own question, but I wanted to throw some ideas out there for you.
First, you're never going to get the locally-assigned IP address of the computer: that's just not something that the browser is ever going to report. You also probably won't be able to get meaningful identifying "low-level" network protocol information as there are many different approaches to NAT.
The traditional way to solve this, as you mentioned is cookies, but if your users are mostly using anonymous mode, that's not an option, as you say.
Have you considered HTML5 Local Storage? That is accessible in anonymous mode, and you can use it like a session, storing a unique session ID on each client. This means your clients need a relatively modern browser, but hopefully that won't be an issue.
Here's some information about HTML5 local storage:
http://diveintohtml5.info/storage.html
This isn't a slam-dunk, though: the behavior of local storage in anonymous mode is currently debated. There's a good discussion of it here:
http://blog.whatwg.org/tag/localstorage
Another option would be to use a querystring...not a great solution, maybe, and easily foiled by the user (if you're worried about that). When you first land on the page, you can redirect the user to the same page with a querystring containing a unique ID. This approach is burdensome in that you must make sure that querystring is added to every internal link. But it does get around all issues with anonymous browsing.