Código Apache:
Ver originalRewriteEngine On
RewriteBase /
RewriteCond %{HTTP_COOKIE} !^.*nombre-cookie.*$ [NC]
RewriteRule .* /establecer-cookie.php [NC,L]
Obviamente la páginas a la que redirijas deberá crear la cookie, si no vas a entrar en un bucle
Saludos