Actually, I'm in the middle of designing a D&D campaign world with a Wild West feel myself.
IMC, what I did to establish a Wild West feel was to first lay down the foundation. The Wild West has to be on a frontier somewhere. It has to be a good distance from civilized society, or the "wild" part goes away.
My campaign is set on a new continent that has been recently discovered. The controlling "civilized" society is overseas, and tries to extert power on the colonies to get resources from the new continent.
Because resources are scarce, so is the law. One law man has to cover a very large territory, making outlaws common. Heck, many come from the civilized lands just to escape justice.
Wizards in my world are quite rare, because most wizards in my world need alot of formal education. Instead, sorcerers are the norm. Wizards, when they show up, tend to be "citified", though there are a few hedge wizards here and there. This keeps the campaign feeling raw and untamed. There aren't a lot of wizard libraries around. There's not a lot of formal education. It's mostly one-room school houses.
I didn't like the idea of guns and gunpower in my campaign either. If I was going to have guns and magic, why not just play Deadlands?
Instead, I kept the main weapon the sword. By keeping the weapon of choice a sword, I keep the campaign feeling like D&D. To get the idea of a Wild West fighter, though, I used the iajitsu rules from Oriental Adventures. So, when fighters duel, they typically call each other out on the street. There's a long stare down. Then, they quickdraw their blade and try to strike each other down, iajitsu style. After all, spaghetti westerns are based on old samurai movies, right?
Also, I've made my campaign set in a very hot climate, so almost no one wears heavy armor. Most people wear leather or hide. A chain shirt is the most armor most anyone will dare to wear. This helps keep the Wild West feel.
For religions, I have a number of "mercenary gods", all of these gods are worshipped by pilgrims and religious types who have been kicked out of their countries. The most dominant god that is worshipped is a god named Jericho, who is very much a fire and brimstone deity. His preachers constantly stand in the streets and rave about how damnation and hellfire are near; and how everyone must repent. Very much a Deadlands approach to religion.
For the natives, I have a variety of lizardmen who fit the bill for me. There are several tribes of lizardmen in different shapes and sizes. I borrowed the Gator Men from the Iron Kingdoms for one of my tribes.
This is a cool thread. Keep it up!