... the address of another instance of the @Array_Vals array which has now been overwritten.

No. Each lexical variable created in the scope of the for-loop is independent of all the others; it has an independent address. Confirm this for yourself by looking (as Corion suggested) at these referenced arrays with Data::Dumper or some similar utility (I like Data::Dump).

c:\@Work\Perl\monks>perl -wMstrict -MData::Dumper -le
"my @source = qw(a b c foo bar baz fee fie foe);
 ;;
 my @Array_of_ALL_Vals;
 ;;
 for my $iloop (0 .. 3){
   my @Array_Vals;
   @Array_Vals = @source[ 0 .. rand @source ];
   push @Array_of_ALL_Vals,\@Array_Vals;
   print Dumper \@Array_of_ALL_Vals;
   }
 ;;
 print '-----------';
 print Dumper \@Array_of_ALL_Vals;
"
$VAR1 = [
          [
            'a',
            'b',
            'c',
            'foo',
            'bar'
          ]
        ];

$VAR1 = [
          [
            'a',
            'b',
            'c',
            'foo',
            'bar'
          ],
          [
            'a',
            'b',
            'c'
          ]
        ];

$VAR1 = [
          [
            'a',
            'b',
            'c',
            'foo',
            'bar'
          ],
          [
            'a',
            'b',
            'c'
          ],
          [
            'a',
            'b',
            'c',
            'foo'
          ]
        ];

$VAR1 = [
          [
            'a',
            'b',
            'c',
            'foo',
            'bar'
          ],
          [
            'a',
            'b',
            'c'
          ],
          [
            'a',
            'b',
            'c',
            'foo'
          ],
          [
            'a',
            'b',
            'c',
            'foo',
            'bar',
            'baz',
            'fee'
          ]
        ];

-----------
$VAR1 = [
          [
            'a',
            'b',
            'c',
            'foo',
            'bar'
          ],
          [
            'a',
            'b',
            'c'
          ],
          [
            'a',
            'b',
            'c',
            'foo'
          ],
          [
            'a',
            'b',
            'c',
            'foo',
            'bar',
            'baz',
            'fee'
          ]
        ];
[download]