$ perl -lE '
my ($haystack,$needle)=@ARGV;
my $i=0;
my @found;
while(-1 != (my $curidx = index $haystack, $needle, $i)) {
  push @found, $curidx;
  $i = $curidx+1
};
say "found at $_" for @found
' abcsdfabcasegabc abc
found at 0
found at 6
found at 13

##</code><code>##

$ perl -lE '
my ($haystack,$needle,$new)=@ARGV;
while(-1 != (my $curidx = rindex $haystack, $needle)) {
  substr $haystack, $curidx, length($needle), $new
};
say "new string: $haystack" 
' abcsdfabcasegabc abc foo
new string: foosdffooasegfoo

##</code><code>##

s/\Q$str\E/$new/g; # since \E is at the end, it's not really required.