Surely there must be an easier way?

Why? Looks pretty easy. For example:

my @a_indices = (1,3,5);
my @b_indices = (0..9);

@b_indices[@a_indices] = ();
@b_indices = grep defined, @b_indices;

use Data::Dumper;
print Dumper \@b_indices;

__END__
$VAR1 = [
          0,
          2,
          4,
          6,
          7,
          8,
          9
        ];
[download]

How big are your arrays? An CPU inefficient but memory efficient version is:

my @a_indices = (1,3,5);
my @b = map {my $t = $_; (grep {$t == $_} @a_indices) ? undef : $t} 0 
+.. 9;

print join ', ', grep {defined} @b;
[download]

Prints:

0, 2, 4, 6, 7, 8, 9
[download]

On the other hand:

my @a_indices = (1,3,5);
my %hasIndex = map {$_ => undef} @a_indices;
my @b = map {exists $hasIndex{$_} ? undef : $_} 0 .. 9;
[download]

is likely to be faster for large arrays, but at the expense of creating a hash.

A faster way to produce %hasIndex is:

my %hasIndex;
undef(@hasIndex{@a_indices});
[download]

However I wouldn't recommend using that trick in production code.

You might consider Set::IntSpan.

If you have Perl 5.10 you can do

use 5.010;

my @a = (1, 3, 5);
my @b = qw/ 0 x 2 x 4 x 6 7 8 9 /;

print @b[grep { not $_ ~~ @a } 0 .. $#b];

__END__
0246789
[download]

lodin

my @arry = qw{ 10 11 12 13 14 15 16 17 18 };
my @indices = qw{  3 5 1 };

my @remainder = ( 0 .. $#arry );
splice @remainder, $_, 1 for reverse sort { $a <=> $b }@indices;

$,=",";
print @remainder, $/;
__DATA__
0,2,4,6,7,8,
[download]