How to store information in session for anonymous user in a site without a user with uid=0?
If you "have to store some information in session for anonymous users", then you will have to make uid=0 available to Drupal. Because that's the uid that Drupal always uses for anonymous users.

So you'll have to re-create that user with uid=0 (again) if you want this to work. If you would combine this with not granting any permissions to role anonymous, there is not a lot that anybody can do in your site if they are not logged in (apart from things like performing login). Maybe an acceptable work around?

About your "for some reason we have deleted user with id=0": it might be that the user with id=0 never got created before (so that it was never deleted). E.g. if the database of your site was created via some type of database copy (backup and restore) from a dev site to a prod site (using PhpMyAdmin). Forgot the exact scenario, but I've ran in such sites before, which caused problems for anonymous users (which is how we discovered such cases). The solution we used was to simply use PhpMyAdmin, and insert the user with uid=0 in the Drupal database (using PhpMyAdmin).