I've come up with a marvelously efficient way...so far I've only tested with short filenames, though.

sub rand_filename {
    my ($base_len, $ext_len, $charset) = @_;
    my ($filename, $count);
    ++$count*rand() < 1 and $filename = $_ while $_ = glob sprintf q!%
+s!x$base_len.".".q!%s!x$ext_len, map { "{".join(",",split //, $charse
+t)."}" } 1..($base_len + $ext_len);
    $filename
}
print rand_filename( 2, 1, join("","a".."z") );
[download]