Hi Eric and thank you for your reply. Unfortunately it's not the alias on the dock that is corrupted but something inside the application package contents.
I tried to find on the time machine the last backup that worked restoring them to a different location one by one and I found out that the update at September 30 of Safari from v10.0 to v10.0.1 was the one that wasn't working.
Since the System Integrity Protection of El Capitan was enabled, I couldn't even use the Time Machine to restore the working version to the original Applications folder, so I had to reboot holding Cmd+R to the recovery mode, open the terminal and disable it by entering the command "csrutil disable".
After rebooting, I still had to right click the Safari icon, then Get Info and then change the permissions of "Everyone" to Read/Write.
By doing that I could delete the non working copy, enter time machine and restore the last working one.
Even with the SIP turned off, you still have to go through the permissions change step to restore it from the Time Machine.
Last step after I made sure that Safari was now working (even though it was downgraded to the previous version which I don't like from the security point of view), I rebooted again to the recovery mode and re-enabled the SIP by entering the command "csrutil enable" on the Terminal.
I still have the two copies (working and non working) and I'll try to look for differences.
The only strange thing was that the "non working" copy even though it wasn't running from the icon on the dock, neither from the icon on the Applications folder (the icon wouldn't even bounce so the error was before starting the executable), as I mentioned on the original post, I was getting an error even from the terminal with the "open /Applications/Safari.app" but surprisingly I was still able to run it with the command "/Applications/Safari.app/Contents/MacOS/Safari", i.e. by calling the binary directly.