use lib xxx at runtime is effectively unshift @INC, xxx. However, you'll have to have that runtime take effect before you compile further things with use, so I'm not sure exactly how early you need it done.
Also note that this works:
my $extra;
BEGIN { $extra = "some computation here" }
use lib $extra;