Have you considered subclassing HTML::Scrubber? Below, I inject the xrel attribute into each anchor before validation.

$ cat XREL.pm
package XREL;
use strict;
use base 'HTML::Scrubber';

sub _validate {
    my ($self, $t, $r, $a, $as) = @_;

    if ( $t eq 'a' ) {
        $$a{ rel } = 'nofollow';
        push @$as, 'rel' unless grep { /rel/ } @$as;
    }
    $self->SUPER::_validate( $t, $r, $a, $as );
}

1;
[download]

$ cat scrub.pl
#!/usr/bin/perl

use warnings;
use strict;
use XREL;

my $scrubber = XREL->new( allow => [ qw[ a p b i u hr br ] ] );
$scrubber->rules(
        a => {
            href => 1,
            rel => qr/^nofollow$/i,
            '*'  => 0,
        }
);

my $html = q[<a href="http://perlmonks.org">link </a>];
print $scrubber->scrub($html), $/;
$html = q[<a href="http://perlmonks.org" rel="nofollow">link </a>];
print $scrubber->scrub($html), $/;
$html = q[<a href="http://perlmonks.org" rel="xxx">link </a>];
print $scrubber->scrub($html), $/;
$html = q[<a href="http://perlmonks.org" rel="xnofollow">link </a>];
print $scrubber->scrub($html), $/;

__END__
output:
<a href="http://perlmonks.org" rel="nofollow">link </a>
<a href="http://perlmonks.org" rel="nofollow">link </a>
<a href="http://perlmonks.org" rel="nofollow">link </a>
<a href="http://perlmonks.org" rel="nofollow">link </a>
[download]

update:changed xrel="nofollow" to rel="nofollow"