This is what I came up with.

my $rx = qr/
    ([abcd])           # a, b, c, or d -- stored in \1
    .*                 # well, whatever
    (?!\1)             # the next character can't be \1
    ([abcd])           # a, b, c, or d -- stored in \2
    .*                 # y'know, stuff
    (?!\1|\2)          # next thing not \1 or \2
    ([abcd])           # a, b, c, or d -- stored in \3
    .*
    (?!\1|\2|\3)       # next thing not \1, \2, or \3
    [abcd]             # you get the idea
    /x;
[download]

I have a feeling there's still an easier way, but that's not too bad. Here is some testing.

use List::Util qw( shuffle );
use Test::More;

my $tests = 1_000;
plan 'tests' => $tests;

for ( 1 .. $tests ) {
    my $s = join q{}, shuffle 0 .. 9, qw( a b c d );
    ok( $s =~ $rx, "match '$s'" );
}
[download]

Update: See below, ikegami has the better way.