That doesn't fix the problem. The assignment is done earlier than it would have without the BEGIN, but it still happens after the use statement is executed.

While the BEGIN block is executed as soon as it finishes compiling, the same goes for the use statement. Since the use statement is fully compiled before the BEGIN block is fully compiled (i.e. it ends first), the use statement is executed before the BEGIN block is executed, and therefore before the assignment is executed.

Solutions:

my $path;
BEGIN {
   # Code that determines the path and stores it in $path.
   $path = "/www/domain/cgi-bin";
}
use lib $path;
[download]

or

use lib do {
   # Code that determines the path and returns it.
   "/www/domain/cgi-bin"
};
[download]

or

sub get_lib_path {
   # Code that determines the path and returns it.
   return "/www/domain/cgi-bin";
}

use lib get_lib_path();
[download]

or

# Hardcoded
use lib "/www/domain/cgi-bin";
[download]

Update: Clarified the wording.