m//g in a while loop will continue from where it left off last time:

 $s = "head\nstuff\nstuff\ntail\nthis\nthat\nhead\nother stuff\nmore\n
+tail\nand more";;

while( $s =~ m[head\n(.+?)tail\n]smg ) { 
    print ">$1<"; 
};;
>stuff
stuff
<
>other stuff
more
<
[download]