of course ( ;-) ) you can do it and you can even use sessions! But it maybe a lot of work (depending on your site-design) and there are some drawbacks too.

if you can't use cookies, you have to add the session id to every single link on your page (and to forms, as hidden parameter, if you use forms at all) and this may be some work, if you don't have a good framework where you can switch such stuff on/off, but it definitly works.

the biggest drawback for the user is, that the links allways change, thats why if i were you i would offer both options, just check first if the user accept cookies and if he doesnt use the other option.

ciao
knoebi