Here are some extremely minor points:

if (exists $tried{$guess})
  {
     print "\tSkipping $guess - already attempted\n\n";
  }
[download]

If you don't print your progress message ("Guessing: ...) that may also save a tiny bit of time.

I wonder if your shuffle sub could be more efficient if you eliminated all the array ref and wantarray checks, since you always seem to be passing an array and returning an array. Or maybe try shuffle from the Core List::Util module.

This shorter code may save a tiny bit:

  my @temp_chars;
  for (1 .. $length)
  {
     push @temp_chars, (shuffle(@chars))[0];
  }
[download]

  my $guess = "@temp_chars";
[download]

Update: Nevermind that last line (thanks AnomalousMonk)