You should show what code you used in your splice implementation, because it certainly could work, assuming you're using it right.

If I were doing this, and memory weren't a constraint, I would make a new array, and then replace the old one with the new one once done. The reason is that every time you insert into the middle of an array, all elements that follow must be shifted to the right one step, which is relatively expensive. Here's an example of how I would do it:

@array = do {
  my @array2;
  foreach ( @array ) {
    push @array2, $_;
    push @array2, "new_element" if $_ eq 'remove';
  }
  @array2;
};
[download]

Or, avoiding the temporary @array2:

@array = map { $_, ( $_ eq 'remove' ? "new element" : () ) } @array;
[download]

For additional efficiency, you might do it this way instead:

@array = map {    $array[$_], (  ($_+1) % 3 == 0  ?  "new element"  : 
+ ()  )    } 0 .. $#array;
[download]

The latter avoids a full string comparison on each iteration, by keeping track of index number rather than element contents.