cookies disabled

I have made a basic analytics system for a site.

If cookie is not set it redirects them to the cookie setting page, makes the cookie and then goes to another page to check the cookie is set. Outcome of that determines if the cookie was set and therefore if they have cookies enabled or not.

But I need a way to serve users who dont use cookies (and of course search engines), as the site's cookies are only used for tracking it's pointless to remove all usage just because cookies are disabled.

As currently going back to any page will instigate the "cookie is not set" code and therefore will just loop indefinately, is there a way to somehow mark this user as having cookies diabled from then on?

Obviously variables are out as I redirect, $_SESSIONs are not really an option as I declare session_start() on each page for those with cookies (and for admin CP purposes).
$_GET isn't really an option as some pages use get info already,
I could perhaps use $_POST somehow, but I prefer not to post data from every page to another on the site as it becomes annoying when clicking the browser back button.

Any ideas?