How about a more brute force approach (I haven't tested this, so I'm not certain it would work, but on first glance the idea seems plausible)
Send a cookie test value on a blank page with a 0-second refresh where the refresh URL contains the same script name as the original URL plus something like '?login=1'.
Same script uses the additional information (i.e. ?login=1) to test whether the cookie is available or not. Sends the appropriate login page based on this information.
To the end user, there might be a very slight delay while the page refreshes, but it should be negligible.
Script (we'll call it index.php) is accessed the first time. Since the '?login=1' parameter is not included, index.php sends a test cookie on a blank page with the refresh tag in the header:
<meta http-equiv="Refresh" content="0,URL=http://somesite.bar/index.php?login=1">
<!-- Just in case refresh *doesn't* work, user won't be stranded -->
Click <a href="http://somesite.bar/index.php?login=1">
<b>here</b></a> to log in...
Page will almost immediately refresh, using the '?login=1' parameter. The index.php script, detecting the '?login=1' parameter, can now check to see if the test cookie exists and act accordingly.
Okay, maybe it would work, maybe not.
But the idea
might help direct you to the solution. I'll actually test this out when I get a chance, but if it does work (and suits your requirements), enjoy!