If you phrase your problem as: "how do I construct a new list of hrefs that excludes hrefs with certain IDs?", then the grep solution becomes much more obvious.

  # build a hash that contains only excluded IDs
  my %exclude = map { ( $_->{id} => 1 ) } @AoH_one;

  # now keep only those that are not excluded:
  my @keepers = grep { not $exclude{ $_->{id} } } @AoH_all;
[download]

If you actually want to replace @AoH_all with this new list, there is nothing wrong with just assigning back into the same variable:

  @AoH_all = grep { not $exclude{ $_->{id} } } @AoH_all;
[download]

As liz points out, you can use splice if you traverse the indexes in reverse order. You can also track the number of elements remaining.

  # use liz's technique
  foreach my $i ( reverse 0 .. $#AoH_all )
  {
      if ( $exclude{ $AoH_all[$i]{id} } )
      {
          splice @AoH_all, $i, 1;
      }
  }

  # keep track of things manually
  my $n_elt = @AoH_all;
  for ( my $i = 0; $i < $n_elt; ++$i )
  {
      if ( $exclude{ $AoH_all[$i]{id} } )
      {
          splice @AoH_all, $i, 1;
          --$n_elt;
          # whoops, bug here, see update...
      }
  }

  # finally, perl updates the length of @AoH_all for us, so:
  for ( my $i = 0; $i < @AoH_all; ++$i )
  {
      if ( $exclude{ $AoH_all[$i]{id} } )
      {
          splice @AoH_all, $i, 1;
          # whoops, bug here, see update...
      }
  }
[download]

Update

Both of the last two loops have a serious error. After you splice out an element, everything else is shifted down — but the value shifted into $AoH_all[$i] is never examined again. Oops. We can either subvert the increment, or we can switch to only increment if we didn't do any replacement:

  # adjust $i after replacement so it is reexamined:
  for ( my $i = 0; $i < @AoH_all; ++$i )
  {
      if ( $exclude{ $AoH_all[$i]{id} } )
      {
          splice @AoH_all, $i, 1;
          --$i;
      }
  }

  # or, only increment $i if we didn't do a replacement:
  for ( my $i = 0; $i < @AoH_all; )
  {
      if ( $exclude{ $AoH_all[$i]{id} } )
      {
          splice @AoH_all, $i, 1;
      }
      else
      {
          ++$i;
      }
  }
[download]