Las cookies o sesiones no se usan para "validar" a tu usuario ... se usan simplemente para no tener que preguntarle constantemente a tu usuario su "nombre/contraseña" y evitar lo más posible que en tus URL's ronden ese tipo de variables.
No sé por qué no puedes usar sesiones .. pero la otra solución sería usar cookies si o sí, .. no puedes hacer más que avisar que tu sistema REQUIERE de uso de cookies y se acabó el cuento. El que no las acepte no podrá usar tu sistema (eso es problema del usuario .. si quiere usar tu aplicación ya las aceptará ..) Lo importante es que AVISES de este o cualquier otro hecho al respecto.
Lo otro que puedes usar es autentificación HTTP (si usas Apache como servidor HTTP y configurado como módulo PHP (no como CGI))
http://www.php.net/manual/es/features.http-auth.php
Y la peor solución es que "preguntes" siempre a tu usuario su nombre/contraseña (que se autentifique) a cada acción que lo requiera usando un formulario y a ser posible en metodo "POST" para que se vean lo mínimo posible y no quede rastro de esas variables en historiales de navegadores .. NUNCA! propages por el URL tu "usuario/contraseña" .. para eso mejor no hacer nada.
Un saludo,
PD: Te recomiendaría solventar esos problemas con las sesiones .. Las sesiones no sólo són útiles para gestión de "autentificación/validación" de usuarios.
Un saludo,