Slight improvement, now around 400% faster, at the expense of readability. I got rid of the parameter passing to the cached subs by using $_. Also, I unrolled the last iteration replacing a substr($string,0,length($string)) with just $string. I tried unrolling the first iteration into a split() but that was slower.

{
  my @cache;
  sub substrings {
    $_ = shift;
    return &{$cache[length($_)]}
      if exists $cache[length($_)];

    my $sub = 'sub { return (';
    foreach my $len (1..length($_)-1) {
      foreach my $off (0..length($_)-$len) {
        $sub .= "substr(\$_,$off,$len),";
      }
    }
    $sub .= "\$_)};";
    $cache[length($_)] = eval $sub;
    return &{$cache[length($_)]};
  }
}
[download]

The only trick I have left is Inline::C... I'll leave that as an exercise for the reader.

-sam