Unable to flash CWM recovery to GS3 over stock 4.1 with Heimdall
While writing the question I found the solution.
Explanation
In Odin Mode, when the phone accepts a new recovery to be flashed, the original Samsung recovery of 4.1 ROM automatically does everything to avoid being flashed, that's actually re-flashing itself on reboot, just like a good ol' computer virus!
Solution
Run Heimdall with --no-reboot flag, or if you are using Odin for Windows, uncheck the auto reboot checkbox.
When flashed, physically remove battery and disconnect USB power supply. Congratulations, you just have ClockworkMod recovery installed!!