Tested variants that don't need @data:

print "@$_\n" foreach sort {
  $a->[0] <=> $b->[0] or
  $a->[1] cmp $b->[1] or
  $a->[2] cmp $b->[2]
} map {
  my ($s,$v)=@$_;
  map {[$v->{$_}, $s, $_]} keys %$v;
} map {
 [$_,$hash->{$_}]
} keys %$hash;
[download]

print "@$_\n" foreach sort {
  $a->[0] <=> $b->[0] or
  $a->[1] cmp $b->[1] or
  $a->[2] cmp $b->[2]
} map {
  my $s = $_;
  map { [ $hash->{$s}{$_}, $s, $_] } keys %{$hash->{$s}}
} keys %$hash;
[download]

I would definitely use a secondary data structure like @data. As a wise man once said,

"Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live."