$test =~ s{
   (
      <a\s
      (?:(?!target=|>).)*
      href="http://
      (?:(?!target=|>).)*
   )
   (?=>)
}{$1 target="_blank"}xsgi;
[download]

Alternatively, the following *might* be faster, especially considering href is usually the first attribute:

$test =~ s{
   (
      <a\s
      (?:(?!href=|target=|>).)*
      href="http://
      (?:(?!target=|>).)*
   )
   (?=>)
}{$1 target="_blank"}xsgi;
[download]

Tested.

Update: Collapsed (?!..re1..)(?!..re2..) into (?!..re1..|..re2..)