One way to do this is with an iterator, like the "odometer" example from Chapter 4 of Dominus's Higher-Order Perl, here's a version of that. The advantage is that it only generates each item of the sequence on demand. Note it doesn't necessarily need to be in a package, I just did that so I could overload the <> operator, it's also possible to just call the code reference returned by new as $odo->(). This doesn't implement the "starting from an arbitrary point" that you mention, because it depends a bit on how that starting point is provided to you - is it a number of iterations, or an existing string like "abcd"?

Update 2019-10-05: I've now released Algorithm::Odometer::Tiny!

use warnings;
use strict;

{
    package Odometer;
    use overload '<>' => sub { shift->() };
    sub new {
        my $class = shift;
        my @w = map { [ 1, ref eq 'ARRAY' ? @$_ : $_ ] } @_;
        my $done;
        return bless sub {
            if ($done) { $done=0; return }
            my @cur = map {$$_[$$_[0]]} @w;
            for (my $i=$#w; $i>=0; $i--) {
                last if ++$w[$i][0]<@{$w[$i]};
                $w[$i][0]=1;
                $done=1 unless $i;
            }
            return wantarray ? @cur : join '', @cur;
        }, $class;
    }
}

my $odo = Odometer->new( (['0'..'9','a'..'z']) x 4 );

my $cnt=0;
while (<$odo>) {
    print $_;
    last if ++$cnt>=100;
    print ', ';
}
print "\n";

__END__
0000, 0001, 0002, 0003, 0004, 0005, 0006, 0007, 0008, 0009, 000a, 000b
+, 000c, 000d, 000e, 000f, 000g, 000h, 000i, 000j, 000k, 000l, 000m, 0
+00n, 000o, 000p, 000q, 000r, 000s, 000t, 000u, 000v, 000w, 000x, 000y
+, 000z, 0010, 0011, 0012, 0013, 0014, 0015, 0016, 0017, 0018, 0019, 0
+01a, 001b, 001c, 001d, 001e, 001f, 001g, 001h, 001i, 001j, 001k, 001l
+, 001m, 001n, 001o, 001p, 001q, 001r, 001s, 001t, 001u, 001v, 001w, 0
+01x, 001y, 001z, 0020, 0021, 0022, 0023, 0024, 0025, 0026, 0027, 0028
+, 0029, 002a, 002b, 002c, 002d, 002e, 002f, 002g, 002h, 002i, 002j, 0
+02k, 002l, 002m, 002n, 002o, 002p, 002q, 002r
[download]