Here is an HTML::Parser API2 example that show you the basics. You basically need to deal with 2 cases - one where you have a </p> and one where you don't. You need to maintain state between the callbacks so you know what to do.

my $data=<<DATA;
<p>foo
<h4>h4.1</h4>
<p>bar
<p>baz
<h4>h4.2</h4>
<p>bar</p>
<p>baz</p>
<h4>h4.3</h4>
<hr>
<p>bar
<p>baz
DATA


{
    package MyParser;
    use base 'HTML::Parser';
    sub start {
        my($self, $tagname, $attr, $attrseq, $origtext) = @_;
        if ( $self->{blockquote} ) {
           # deal with no closing </p>
           print "</blockquote>\n$origtext";
           $self->{blockquote} = 0;
        }
        elsif ( $tagname eq 'p' and $self->{h4last} ) {
            print '<blockquote>';
            $self->{blockquote} = 1;
        }
        else {
           print $origtext;
        }
        $self->{h4last} = $tagname eq 'h4' ? 1 : 0;
    }
    sub end {
        my($self, $tagname, $origtext) = @_;
        if ( $self->{blockquote} and $tagname eq 'p' ) {
           print '</blockquote>';
           $self->{blockquote} = 0;
        }
        else {
           print $origtext;
        }
    }
    sub text {
        my($self, $origtext, $is_cdata) = @_;
        print $origtext;
    }
    sub comment {
        my($self, $origtext ) = @_;
        print $origtext;
    }
}

my $p = MyParser->new;
$p->parse($data);
[download]