In the campaign I am playing the gods were banned from the land so you can't play as a cleric or wizard. I want to play a walker in the waste prestige class but the requirement of casting at least three spells of the Sand or Thirst domain as divine spells is hard without the cleric. I don't want to play as a druid because I want to be a melee character. the paladins don't have access to spells without the gods and the ranger takes to long. It as to be written in a book somewhere and the dragon magazines aren't available.
There are several base classes with divine spellcasting that are neither Cleric nor Druid. Here's a list of ones I can find (ignoring "half spellcasting" classes like Ranger and Paladin, which only get up to 4th level spells):
- Adept: An NPC class. Basically the only interesting thing about it is that it can cast some normally-arcane spells as divine spells, which is useful for fulfilling the occasional weird prerequisite. Other than that, it's pretty much a crappy version of a Cleric. You probably don't want to play this, but listed here for completeness.
- Archivist (Heroes of Horror): A wonky cross between a Wizard and a Cleric. Has the ability to learn and prepare spells from any divine spellcasting list. Can be an effective melee bruiser for the same reason as a Cleric; buff spells are really good.
- Divine Bard: A variant of the PHB Bard class that has a slightly different spell list and casts divine spells. Like the regular Bard, only gets spells up to level 6.
- Favored Soul (Complete Divine): Casts off of the Cleric spell list, but learns and casts its spells spontaneously, like a Sorcerer. Generally considered worse than Cleric for most purposes, but can be a nice change of pace.
- Mystic Ranger (Dragon Magazine #336): A variant Ranger that trades delayed progression in normal Ranger class features for better spellcasting. Has a weird spellcasting progression where it's on the Sorcerer schedule (level 2 spells at level 4, level 3 spells at level 6, etc.) until it hits level 5 spells at level 10, then stops learning new spell levels. This makes it extremely strong for the first half of the game (it's basically T1 spellcasting tacked onto the Ranger chassis), but then it falls off pretty hard at high levels. Combine with the Sword of the Arcane Order feat (Champions of Valor) for extra spellcasting goodness. As pointed out by Hey I Can Chan, this class also has some caster level weirdness due to inheriting the base Ranger class' text despite a different spell progression; ask your DM how caster level works if you want to use this variant.
- Sha'ir (Dragon Compendium vol. 1): A combined arcane/divine spellcasting class. Has a weird spellcasting mechanic where you go send a little elemental buddy to physically fetch your spells. Primarily casts off of the Sorcerer/Wizard list, but can also get other spells (including divine spells). Probably not a great fit for your needs; it's focused much more on its spellcasting than any support for being a melee bruiser.
- Shugenja (Complete Divine): An elemental-themed divine spellcaster. Sorta similar to a Cleric, but with a more limited spell selection.
- Spirit Shaman (Complete Divine): A nature-and-spirits-themed divine spellcaster. Casts off of the Druid list, but generally gets much worse class features than a Druid.
Not all of the above classes natively have enough spells from the Sand and Thirst domains natively to qualify for Walker in the Waste, but you can look into ways of getting bonus domains, such as the Contemplative prestige class (Complete Divine), or any of the others listed under the "Bonus Domains" section of the ever-helpful Lists of Stuff. Using these to pick up Sand or Thirst as a bonus domain will likely solve your spell access problem.
The Favored Soul (Complete Divine, p6) is basically the Sorcerer to the Cleric's Wizard. They have a 3/4 BAB and all good saves, but they don't get domains or heavy armor proficiency.
Complete Divine also has the Shugenja (casts divine spells like a sorcerer, but has a specific list; they have a shtick relating to the elements) and Spirit Shaman (casts divine spells, also like a sorcerer; has a druidic feel). I haven't personally played/seen those classes, but a quick scan doesn't reveal anything terribly breaking (for good or ill) - they all get 9th level spells and the other abilities aren't obviously stupid or stupidly powerful.
All of that said, there is absolutely nothing preventing a melee-focused druid, especially if you take full advantage of your animal companion (always have a flanking buddy, for one). Sure, they can't wear metal armor, but they can wild shape into a grizzly bear and then still cast spells (with Natural Spell, of course). There's an argument to be made that "wild shape" is more powerful than "fighter" at pretty much any given level.