No one can login and access denied message
The problem was ip_geoloc module. It was messing up $_SESSION variable, a solution is given on the issue queue (for now!) and the module author agrees with it. It's highly probable that it is happening because of a mis-configuration by me. The user was successfully logged in but immediately their session was invalidated. Somehow disabling it was not enough and it's directory had to be moved out of Drupal root. I am 100% sure not any of it's functions or APIs are used anywhere else. Maybe some cache problem?
Lesson learned:
When having signing-in problem, try to check the $_SESSION variable on the server using devel and it's helper functions (e.g dpm, dsm, dd, ... or as a last resort var_export) and not with you google/firefox developers console.
This is the third time I'm facing this strange behavior and the first time I was able to fix. If you are having this problem, try to follow this checklist:
Ask yourself:

Does truncating the sessions table fix the problem?
Does forcing a change for user password fix the problem?
Have you added any particular configuration to your settings.php? e.g base_url, cookie_domain, ...
Does UID 0 exist in your database (i.e anonymous user)?
Is any redirection module installed? search404, redirect, global_redirect,...
Do you have a custom module enabled?
Is there any problems with your theme?
Do you have any path altering modules, e.g path_alias?
Do you have any module changing the log-in behavior? e.g logintoboggan
Have you enabled any caching module? e.g authcache, memcache, session_cache, boost, varnish, ...
Do you have any access control module enabled? e.g workbench, content_access, acl, og_access, ...
And finally, have you enabled any module which changes the user $_SESSION? e.g session_api, session_cache, ip_geoloc, ...

Places to look / Things to do

Look at drupals watchdog messages. If you can not log-in, use drush watchdog-show --tail to see what's happening.
If running apache and mod-php, look in apache's error log, usually at /var/log/apache/error_log for *nix systems.
If running php-fpm, see the php-fpm log, make sure there is no communication problem with php daemon, such as headers are not lost. if you see no error log try running your site with drush/php internal server. the command is drush rs or drush rs the.ip.goes.here:thePort
make a fullbackup, disable all modules with this command AFTER making a full backup (you can make a backup with drush ard or just database drush sql-dump &gt; db.sql or use backup_migrate module)drush dis -y $(drush pml --nocore --status=enabled --pipe) -&gt; this command only works in *nix systems I don't know the direct translation for windows.
Set your default theme to something... safe! such as seven or garland. If you can not log-in use this drush commands:drush en seven &amp;&amp; drush vset theme_default seven;
Monitor $_SESSION variable with any debugging tool, see if it's content are correct, ok, healthy.
For all the processes and daemons involved in serving a request (nginx, php-fpm, apache, varnish...) make sure they all have write access to their tmp directory.

Good luck debugging!