We can just use the shuffle algorithm slightly modified to suit our needs :

use Inline C => <<'END_OF_C_CODE';

void cderange(SV* array_ref) {
  AV* array;
  I32 index, i;
  SV** sv_1, **sv_2;
  SV* sv_temp;

  if (! SvROK(array_ref))
    croak("array_ref is not a reference");

  srand(time( NULL ));
  array = (AV*)SvRV(array_ref);
  index = av_len(array);
  for (; index; index--) {
    i = (I32) (rand() % (index));
    sv_1 = av_fetch(array, index, 0);
    sv_2 = av_fetch(array, i, 0);
    sv_temp = *sv_1;
    *sv_1 = *sv_2;
    *sv_2 = sv_temp;
  }
  return;
} 

END_OF_C_CODE 

sub derange {
  my $first = $_[0];
  cderange \@_;
  if( $first eq $_[0] ){
    ($_[0], $_[1]) = ($_[1], $_[0])
  }
  return @_;
}
[download]

This is fast, but don't work very well with very big arrays (size over RANDMAX, usually 32000).

Oops.. Sorry, the wrapper performs unnecessary operations, here a good version :

use Inline C => <<'END_OF_C_CODE';

void cderange ( SV* truc, ... ){
  SV* sv_temp;
  I32 index, i;
  Inline_Stack_Vars;

  srand(time( NULL ));
  index = Inline_Stack_Items;
  for (; index; index--) {
    i = (I32) (rand() % (index));
    sv_temp = Inline_Stack_Item(index);
    Inline_Stack_Item(index) = Inline_Stack_Item(i);
    Inline_Stack_Item(i) = sv_temp;
  }
  Inline_Stack_Done;
}

END_OF_C_CODE
[download]

Very fast, but this code is subject to the same caveat as Algorithm::Numerical::Shuffle.