Silly idea but, as you say, the decision is out of you hands :-(

Set up the four sets already shuffled then make an array of references to them. Then create another array with a guaranteed one from each set (0 .. 3) then a random selection of four more from any set. Then shuffle the order. Finally, build the password by concatenating random letters from the sets in the already shuffled order.

knoppix@Microknoppix:~$ perl -MList::Util=shuffle -Mstrict -wE '
my @lc  = shuffle q{a} .. q{z};
my @uc  = shuffle q{A} .. q{Z};
my @dig = shuffle q{0} .. q{9};
my @oth = shuffle qw{ ! " £ $ % ^ & * _ - + = @ ~ };
my @all = \ ( @lc, @uc, @dig, @oth );

my @order = ( 0 .. 3 );
push @order, int rand 4 for 1 .. 4;
@order = shuffle @order;

my $passwd = q{};
$passwd .= $all[ $_ ]->[ rand @{ $all[ $_ ] } ] for @order;

say $passwd;'
E5yR=$%£
knoppix@Microknoppix:~$
[download]

Runs of this have produced &D0%@nn%, F9@F=Rc1, S~j@3WgG, 633P£m!T and o8S4pl!! so, as long as there is no stipulation barring repeated characters, this seems to work.

I hope this is useful.

Update: If repeated characters are not wanted then you can use splice to remove the chosen character from the array so it can't be re-used.

...
$passwd .= splice @{ $all[ $_ ] }, rand @{ $all[ $_ ] }, 1
   for @order;
...
[download]