Clustering unique visitors by useragent, ip, session_id
One possibility here (and this is really an extension of what Sean Owen posted) is to define a "stable user."

For the given info you have you can imagine making a user_id that is a hash of ip and some user agent info (pseudo code):

uid = MD5Hash(ip + UA.device + UA.model)


Then you flag these ids with "stable" or "unstable" based on usage heuristics you observe for your users.  This can be a threshold of # of visits in a given time window, length of time their cookies persist, some end action on your site (I realize this wasn't stated in your original log), etc...

The idea here is to separate the users that don't drop cookies from those that do.

From here you can attribute session_ids to stable uids from your logs.  You will then have "left over" session_ids for unstable users that you are relatively unsure about.  You may be over or under counting sessions, attributing behavior to multiple people when there is only one, etc...  But this is at least limited to the users you are now "less certain" about.

You then perform analytics on your stable group and project that to the unstable group.  Take a user count for example, you know the total # of sessions, but you are unsure of how many users generated those sessions.  You can find the # sessions / unique stable user and use this to project the "estimated" number of unique users in the unstable group since you know the number of sessions attributed to that group.

projected_num_unstable_users = num_sess_unstable / num_sess_per_stable_uid


This doesn't help with per user level investigation on unstable users but you can at least get some mileage out of a cohort of stable users that persist for some time.  You can, by various methods, project behavior and counts into the unstable group.  The above is a simple example of something you might want to know.  The general idea is again to define a set of users you are confident persist, measure what you want to measure, and use certain ground truths (num searches, visits, clicks, etc...) to project into the unknown user space and estimate counts for them.

This is a longstanding problem in unique user counting, logging, etc... for services that don't require log in.