Идентификация посетителя сайта

Но только как можно произвести идентификацию пользователя, если он не зарегистрирован и не записан ни в каких куки?

Записать его, разумеется. После того как пользователь будет идентифицирован с помощью куки, можно будет добавить его идентификатор вместе с ид товара в таблицу MySQL.

Сессии не слишком хорошо подходят для такой задачи, в силу заведомо ограниченного времени жизни.

Используйте сессии. Даже у незарегистрированных пользователей есть идендификатор сессии, который также можно сохранить в БД если надо и использовать в качестве ключа.