It works with exec. I have some scripts which set ORACLE_HOME and LD_LIBRARY_PATH like so:

BEGIN {
   unless ($ENV{BEGIN_BLOCK}) {
      $ENV{ORACLE_HOME}  = "/oracle/product/current";
      $ENV{LD_LIBRARY_PATH} = "$ENV{ORACLE_HOME}/lib";
      $ENV{BEGIN_BLOCK} = 1;
      exec $^X, $0, @ARGV;
   }
}
[download]

This works fine. Careful readers will see that I don't exec env. It doesn't appear to be necessary.