...to create the number of foreach loops dynamically, however, don't know if that is even possible

Of course it's possible -- this is Perl! :-)

Here's a rewrite of your program using a subroutine dynamic_assign, which I think does what you want:

#!/usr/bin/perl -w

# Always use strict & warnings!
use strict;
use warnings;

# User-data
my @array = (
    ['john','tom','peter'],
    ['rose','teak'],
    ['car','truck','jeep'],
    ['trees','plants'],
    ['good','bad','ugly'],
);

my @arrayindex = (4, 2, 1);
my %hash = ();

# Main program

#
# The "hard-wired" (ie. original) way to do it
#
# foreach my $i (@{$array[$arrayindex[0]]}) {
#     foreach my $j (@{$array[$arrayindex[1]]}) {
#         $hash{"$i $j"}=1;
#     }
# }

# The "new" way (using a recursive subroutine)
dynamic_assign(\@arrayindex, \@array, \%hash);

foreach my $i (keys %hash) {
    print "$i=>$hash{$i}\n";
}


# Subroutines

#
#  Inputs
#    $1 ... a pointer to a list of indices (eg. [ 4, 2, 1, 5])
#    $2 ... a pointer to a list of lists (see @array in the main progr
+am)
#    $3 ... a pointer to a hash
#
#    $4 ... (when recursing) the current index into the list of indice
+s
#    $5 ... (when recursing) the accumulated key
#
#  Results:
#    Assigns each final key of the hash to 1.
#
sub dynamic_assign {
    my ($pindices, $parray, $phash, $idx, $key) = @_;

    # The 1st time -- initialize index and key
    defined($key) or ($idx, $key) = (0, "");

    if ($idx < @$pindices) {
        # Use each value of the selected array
        my $index = $pindices->[$idx];
        foreach my $value (@{$parray->[$index]}) {
            my $newkey = $key? "$key $value": $value;
            # Here comes the recursion...
            dynamic_assign($pindices, $parray, $phash, $idx+1, $newkey
+);
        }
    } else {
        # Final assignment
        $phash->{$key} = 1;
    }
}
[download]

It lets you specify what indices you want in @arrayindex, and then calls the subroutine dynamic_assign which takes care of the rest.  The "magic" part is that dynamic_assign calls itself recursively, so that every necessary hash key is generated.