A bit late, perhaps, but:

1) I agree that overgenerating and then filtering out unwanted strings is a Bad Idea (too redolent of a bogosort for my liking :).

2) The code below uses the four character classes implicit in the OP.

use strict;
use warnings;

my $password_length = 8 + rand 3;  # Or whatever (here 8-10 chars)
my @classes = ( qw/ upper lower digit punct / );

my @pattern;
for ( 1 .. $password_length ) {
  my @tmp = grep { $_ ne last2( \@pattern ) } @classes;
  push @pattern, $tmp[ rand @tmp ];
}

my %chars;
for my $class ( @classes ) {
   @{ $chars{$class} } = map { chr =~ /[[:$class:]]/g } 0 .. 127;
}

my $password = join '', map ${ $chars{$_} }[ rand @{ $chars{$_} } ], @
+pattern;
print $password;

sub last2 {
  my $to_check = shift;
  return 'ok' if @{ $to_check } < 2;
  return $to_check->[ -1 ] if $to_check->[ -1 ] eq $to_check->[ -2 ];
  return 'ok';
}
[download]

That said, if I were to be issued a password like |V$w`'N#^8, I wouldn't hesitate to write it on a post-it and stick it on my monitor!