I also have an inkling that we can eliminate the backtracking in sauoq's program (or maybe not...).

Your intuition is right. My (much nicer) second try below generates a valid solution string without backtracking. Notice it isn't the same string as my original answer though. (Nor is it a permutation.)

#!/usr/bin/perl -w
use strict; 

my $string = '9999';  # Starting with nines simplifies the loop
my %seen = ( $string => 1 ); 
my $seen = 1;

while ($seen < 10000) {
    for (0 .. 9) {
        my $candidate = substr($string, -3) . $_; 
        next if $seen{$candidate}; 
        $string .= $_;
        $seen{$candidate} ++; 
        $seen++; 
        last;
    }
}

print $string, "\n";
[download]

-sauoq
"My two cents aren't worth a dime.";