I got a Stunky and its ability is Stench, but I don't know if I need it in the first slot for it to work or not.
Yes, the Stunky has to be the 1st Pokemon in the party for Stench to take effect.
http://bulbapedia.bulbagarden.net/wiki/Stench_(ability)