I actually used a Monte Carlo method as a first try, before enumerating all possibilities. I made the mistake of making it way too general, but it does in fact make the rolls.

#!/usr/bin/perl -w

use strict;
srand;

my $iters = $ARGV[0] ? $ARGV[0] : 10;
my $sum = 0;

my $numdice = 4;
my $sides = 6;

sub dice ($$) {
        my ($num,$sides) = @_;
        my @ret = ();
        my $min = $sides;
        for (1..$num) {
                my $roll = int(($sides)*rand)+1;
                $min = $roll < $min ? $roll : $min;
                push @ret, $roll;
        }
#       print "rolled [@ret]; min $min\n";
        my $sum = 0;
        foreach (@ret) { $sum += $_ }
        return $sum - $min;
}

for (1..$iters) {
        $sum += dice($numdice,$sides);
} # main loop

print "average over $iters rolls is ".($sum/$iters)."\n";
[download]

Yeah; that's just kinda pasted in from the quick-n-dirty scratchbox. It gives the right result, which was what I was interested in at the time. Someday my code will start to look nicer, but this will require time. Time, and friends asking me to do weird tasks using Perl.

I wanted a precise answer, and the friend who asked me to do the computation asked me why I didn't just enumerate all 6**4 possible 4d6 rolls, and go from there. So I did.