Whenever running a benchmark, you should, as much as possible, take out things that you are not comparing and use functions/operations that are as low cost as possible (in comparison to what you're comparing). That call to rand() is slowing things down alot, and if you remove it, you get a better comparison:

#!/usr/local/bin/perl -w

use strict;
use Benchmark;

my $i = 0;

timethese(200000, {
 RAND_AND=>\&and_rand,
 RAND_MOD=>\&mod_rand,
 TWO_AND=>\&two_and,
 TWO_MOD=>\&two_mod,
});

sub and_rand {
  my $num = rand(2**31);
  return $num & 1;
}

sub mod_rand {
  my $num = rand(2**31);
  return $num % 2;
}

sub two_mod {
 $i++ % 2;
}

sub two_and {
 $i++ & 1;
}
~
"tst" 31 lines, 359 characters 
~/tst>./tst
Benchmark: timing 200000 iterations of RAND_AND, RAND_MOD, TWO_AND, TW
+O_MOD...
  RAND_AND:  1 wallclock secs ( 1.12 usr +  0.00 sys =  1.12 CPU) @ 17
+8571.43/s (n=200000)
  RAND_MOD:  0 wallclock secs ( 1.10 usr +  0.00 sys =  1.10 CPU) @ 18
+1818.18/s (n=200000)
   TWO_AND:  0 wallclock secs ( 0.36 usr + -0.01 sys =  0.35 CPU) @ 57
+1428.57/s (n=200000)
            (warning: too few iterations for a reliable count)
   TWO_MOD:  2 wallclock secs ( 0.42 usr + -0.00 sys =  0.42 CPU) @ 47
+6190.48/s (n=200000)
~/tst>
[download]

Update: Even the ++ in the other two subroutines is a sort of unwanted operator. If I take it out and set $i to a constant, the AND method is almost twice as fast as the MOD method (ok, on second checking maybe that twice as fast was a fluke, its more like 30-40% faster consistently).