How about a roll-you-own binary string to base converter?

our $ZERO = Math::BigInt->new(0);
our $ONE = $ZERO + 1;

# Convert a bitstring (only 1s and 0s) to a number,
# as if it were a representation of the given base.
sub bitstring_to_base {
    my $result = $ZERO;
    my $pow    = $ONE;

    for my $bit (reverse split '', $_[0]) {
        $result += $pow if $bit;
        $pow *= $_[1];
    }
    return $result;
}

# Skips over 0 and 1.
sub make_iter {
   my ($base) = @_;

   my $num = Math::BigInt->new(1);

   return sub {
      $num->binc;
      return Math::BigInt->new(
          bitstring_to_base($num->as_bin() =~ s/^0?b//r,
                            $base)
      );
   };
}
[download]

Also, the line in make_iter could take a value other than 1, as a power-of-ten starting point in a search:

my $num = Math::BigInt->new("1" . ("0" x (ARGV[1] // 0)));
[download]