First, a corrected version of the code as you wrote it:

#!/usr/bin/perl -w
use strict;
use Data::Dumper;
use Carp;

# If possible we prefer not to use any CPAN module
# or regex. It's for my understanding


my $seed = $ARGV[0] || "000";
# Seed can be longer than 3 digits but always 0,1,2,3

for (my $i = 0; $i < length($seed); $i++) {

  # First loop is to generate 1 position differ
  for (my $bs=0; $bs<=3; $bs++) { 

    my $bval = $bs;
    if ( substr($seed,$i,1) == $bs) {
      #$bval = 0;
      next;
    }

    my $ns = $seed;
    substr($ns,$i,1,$bval);
    print "$ns";


    # Second loop for tags in 2 positions differ

    for (my $j=($i+1); $j < length($seed); $j++) {

      for (my $cs = 0; $cs<=3;$cs++) {

        my $cval = $cs;
        if (substr($ns,$j,1) == $cs) {
          #$cval = $cs;
          next;
        }

         my $ns2 = $ns;
         substr($ns2,$j,1,$cval);
         print "\t$ns2";

      }
    }
    print "\n";
  }
}
[download]

(Note that I also fixed the outer loop to give its variant digits in order instead of substituting 0 in the original value's place.)

Now, that works, but it's very C-accented Perl and the variable names are pretty cryptic, plus it uses a couple modules that aren't actually used in the code. Here's another version which cleans all that up:

#!/usr/bin/perl
use strict;
use warnings; # "use warnings" tends to be preferred over "-w"

# Seed can be longer than 3 digits but always 0,1,2,3
my $seed = $ARGV[0] || "000";
if ($seed =~ /[^0-3]/) {  # "If $seed contains anything other than 0,1
+,2,3"
  die "Invalid seed.  Seed may only contain digits from 0 through 3.\n
+";
}

# First loop is to generate 1 position differ
for my $i (0..length($seed) - 1) {
  for my $first_diff (0..3) {
    next if (substr($seed, $i, 1) == $first_diff);

    my $outer_variant = $seed;
    substr($outer_variant, $i, 1) = $first_diff;
    print "$outer_variant";

    # Second loop for tags in 2 positions differ
    for my $j ($i+1..length($seed) - 1) {
      for my $second_diff (0..3) {
        next if (substr($outer_variant, $j, 1) == $second_diff);

        my $inner_variant = $outer_variant;
        substr($inner_variant, $j, 1) = $second_diff;
        print "\t$inner_variant";
      }
    }
    print "\n";
  }
}
[download]

I did use one regex, even though you requested that they not be used, because it's the quickest way to verify that $seed is valid and any other way to validate it would have been much more complex.

Finally, just for fun, let's do it recursively, so that you can easily produce any number of differing positions instead of being limited to 1-2:

#!/usr/bin/perl
use strict;
use warnings;

# Seed can be longer than 3 digits but always 0,1,2,3
my $seed = $ARGV[0] || "000";
if ($seed =~ /[^0-3]/) {
  die "Invalid seed.  Seed may only contain digits from 0 through 3.\n
+";
}

my $max_differences = 2;

frobnicate($seed);

sub frobnicate {
  my ($prefix, $suffix, $difference_count) = @_;
  unless (defined $suffix) {
    $suffix = $prefix;
    $prefix = '';
  }

  $difference_count++;

  while (length $suffix) {
    my $initial = substr($suffix, 0, 1);
    substr($suffix, 0, 1) = '';

    for my $substitute (0..3) {
      next if $substitute == $initial;

      print "\t" unless $difference_count == 1;
      print $prefix, $substitute, $suffix;

      if ($difference_count < $max_differences && length $suffix) {
        frobnicate($prefix . $substitute, $suffix, $difference_count);
      }

      print "\n" if $difference_count == 1;
    }
    $prefix .= $initial;
  }
}
[download]