I was just reading about Shellshock and how it works. From what I understood it exploits the fact that the code is being executed even after the export of the function definition which is exported as an env variable.
Why isn't the fact that you can set environmental variables on a server a big security issue of its own?
The attacker isn't setting environment variables on his own. What's happening is that the CGI specification for communication between a web server and CGI executables says that a number of parameters (such as HTTP headers) are to be passed as environment variables.
This means that an attacker can't set sensitive variables such as PATH or LD_LIBRARY_PATH, but they do have control over ones such as HTTP_USER_AGENT. The "shellshock" attack doesn't care what environment variables it uses, it just needs the ability to make one of them (any one) look like a bash function.
Another source of vulnerability are the HTTP headers like Authorization or Referer. This can be maliciously formed to inject some Bash command. Note, all commands will be executed with the privilege of the user the mod_cgi is running.
Like Mark said, the environment variables aren't set on the server. Rather, they're values that are (non-arbitrarily) chosen and passed as environment variables.
For an idea of how this is abused, here is a blog post from two days ago with the HTTP_USER_AGENT targeted specifically.
