You can can accomplish that for-loop without eval using NestedLoops from tye's Algorithm::Loops. And instead of eval'ing that anonymous sub to only work with a set number of indices, you can use a function that takes an arbitrary list of indices to dereference (which answers your main question).

use Algorithm::Loops 'NestedLoops';

## returns an alias to $_[0]->[ $_[1] ]...[ $_[-1] ]
sub deref_many : lvalue {
    my $ptr = \shift;
    $ptr = \$$ptr->[$_] for @_;
    $$ptr;
}

my @array;
my @size = (4, 5, 6);

NestedLoops(
  [ map [0 .. $_-1], @size ],
  sub { deref_many(\@array, @_) = rand }
);
[download]

The lvalue sub might be a tad too cutesy, but I think its usage at the bottom reads fairly well (since you want to use $a[x][x]..[x] as an lvalue)

While all of this might be cleaner, and it avoids eval, I would imagine that your initial eval solution is going to be fastest, since it doesn't involve any function call overhead.