Your example looks essentially trivial, so I wonder if there's a larger problem that you are trying to solve ?

The obvious bit-twiddling way to do this is:

  my $b = 7 ;              # Number of bits to worry about
  my $p = ($b + 1) >> 1 ;  # Number of pairs of bits to consider
  my $cnt = 0 ;
  for my $v (0..((2**$b)-1)) {
    my $m = 0b11 ;
    for (1..$p) {
      if ($v & $m) { $m <<= 2 ;      }
              else { $cnt++ ; last ; } ;
    } ;
  } ;
[download]

this will work for $v up to the largest unsigned integer supported on your machine -- though it gets tedious waiting.

With $b = 7 you could save time by starting at $v == 85 and $cnt = 84, or more generally:

  ...
  my $iv  = 0 ; for (1..$p) { $iv = ($iv << 2) + 1 ; } ;
  my $cnt = $iv ;
  for my $v ($iv..((2**$b)-1)) {
    ...
[download]

If you want to do this for longer bit-strings than will fit in an unsigned integer, then vec could be your friend... but you may have difficulty counting (also be prepared for a long wait).

If bit-twiddling looks too much like 'C', then:

  my $f = "%0".($b + ($b & 1))."b" ;
  my $cnt = 0 ;
  $cnt += sprintf($f, $_) =~ m/^(?:01|10|11)*00/ for 0..((2**$b)-1) ;
[download]

will do the job. Usually with Perl, the avoiding of explicit loops make things faster. In this case, not (on my machine, anyway).

For limited values of $b you can do things two pairs of bits at a time:

  my $f = "%0".(($b + ($b & 1)) >> 2)."X" ;
  my $cnt = 0 ;
  $cnt += sprintf($f, $_) =~ m/[012348C]/ for 0..((2**$b)-1) ;
[download]

Of course, this is all unnecessarily complicated. For $b bits you have 3**($b >> 1) values where none of the bit pairs are zero. I wonder what the real problem is...