Instead of storing the shell code on the stack, there may be ways of putting it into static buffers. For instance, many network services perform a gethostbyaddr() on the client's address. The DNS resolver library uses a fairly large static buffer to store DNS responses. So, if you have control over your name server, you can make it return DNS records that contain the shell code in their data section.
This type of attack has been used succesfully against the Washington University FTP Daemon, wu-ftpd.