You would need store the IP and timestamps server-side. It's unlikely that a bot would send cookies, and even a URL based session is not reliable.
The overhead of a file should not be too much, unless you are just doing flat-file logging which will kill you. You can use SQLite or similar, perhaps stored on a memory based filesystem for a small speed boost. Or you could go with something like memcached. If you need to persist the data, use MySQL. The overhead of a full-blown database is practically nothing compared with the time it takes PHP to do pretty much anything.
If you really want to do something like this with sessions, display a user agreement page unless there is a defined "I Agree" variable in the session. That way, if a bot doesn't send a valid session back, all it gets is the user agreement. If it does, then you can track it with session variables.
Bear in mind that the session-based solution is not necessary since you don't need to remember client state between requests, and that sessions will incur as much, if not more, overhead than most custom alternatives.
Regarding the statement that session variables can be manipulated by cookies, it's not entirely true. However, if you're silly enough to leave register_globals
on and you ask for a global variable, I wouldn't like to hazard a guess as to whether it came from a session, a cookie, a query string, the environment, or was previously undefined. This is all moot if you explicitly access through $_SESSION of course.