Crie um wrapper sh (preferencialmente traço) em torno do executável no qual você configura o ambiente e, em seguida, execute o destino:
#!/bin/sh
ENVVAR=envvar exec ./target "$@"
O Dash é bastante eficiente, e isso só adiciona cerca de 0,0005s ao tempo de inicialização do destino na minha máquina.
O wrapper C equivalente não será muito mais rápido do que isso:
#include <unistd.h>
int main(int argc, char *argv[])
{
setenv("ENVVAR", "envvar", 1);
execvp("./target", argv);
}