Firstly why the script fails to rotate the letters by one, if I remove either $_++ (I've tested several combinations with and operator, and that didn't work either)?

$x++ returns $x, and increments $x in-place. So the first $_++ increments $_, and the the second instance of $_++ only has the function to return $_; the actual increment it does is lost. You can achieve the same thing with map { $_++; $_ }.

Also that might be just me not fully understanding the implications of the eval string hack

Afaict it does nothing (and I don't see any changed behavior if I remove it).

Also note that your code turns z into aa, a feature not desired for rot13.

but why won't $_++ for 1..13 or $_ += 13 work?

$_++ for 1..13 doesn't work because foreach has its own $_ variable, which is set to the item it currently iterates over. Something like $x++ for 1..13 should work.

 $_ += 13 assumes numeric context, ie it lacks the magic that ++ possesses.