Classes
Five classes stand out to me as ideal choices for entry to warshaper.
Pugilist Fighter
Pugilist is a variant fighter from Dragon vol. 310. It gains Improved Unarmed Strike, slightly increased unarmed strike damage (but it doesn’t scale like the monk’s), the Endurance feat, and then one other feat (or special “Pugilist ability”) of your choice from a decent-size list (comparable to the size of the core fighter bonus feat list, but much smaller when you consider all of the supplement feats that a fighter can usually take). It’s kind of solid for all the feats you get in one level, but I’d definitely not take more than the one.
Pugilists give up martial weapon proficiency, but retain all armor proficiencies.
Knight
Knight gets d12 HD, heavy armor, and Bulwark of Defense and Test of Mettle in the first four levels. You also get the Fighting Challenge, which is OK, and Mounted Combat, which... is maybe useful? Anyway, the first four levels are pretty good (in fact, it is often claimed that knight has five good levels: 1, 2, 3, 4, and 20).
I would only go with knight if I got at least three levels; Bulwark of Defense is a really nice feature. I’d want Test of Mettle if my Charisma was good, but a level of pugilist or crusader could fit in well.
The big problem with knight is the Knight’s Code, which is possibly even stricter than the paladin’s (though the penalty is less severe). It also demands that you remain lawful: that makes it hard to also take a level of barbarian, and you want a level of barbarian, because...
Barbarian
Barbarians can get Improved Unarmed Strike as a bonus feat, but it’s not worth it to do so. Instead, you want a level of barbarian for relevant stat bonuses, d12 HD, and most importantly, the lion spiritual totem from Complete Champion. Pounce gives you absolutely critical mobility.
Warblade
Warblade gets medium armor proficiency, not heavy, but also gets d12 HD, and a number of really useful maneuvers. Tiger Claw can let you attack more often, which is nice, with wolf fang strike and sudden leap.
Crusader
Doesn’t get Tiger Claw like warblade does, and only a d10 HD, but it does get heavy armor proficiency, and more importantly, Devoted Spirit is solid, reliable non-magical healing. Crusaders are the best in-combat healers in the game, while remaining solid martial forces in their own right. Plus Steely Resolve can dramatically improve your ability to remain standing.
Crusader 4 itself could be a solid entry to warshaper, though I’d probably go with levels of barbarian and pugilist first.
Feats
Superior Unarmed Strike
This feat from Tome of Battle gives you a scaling unarmed strike damage similar to (slower than) the monk, if you care. It’s decent enough, particularly when you’re getting size bonuses.
Improved Natural Attack (unarmed strike)
It’s a damage boost that stacks with everything; might as well.
Note that in theory you could replace this with a fanged ring if you were in a game where you could expect to get a 10,000 gp magic item any time soon, but you aren’t
Stone Power
Another feat from Tome of Battle, this allows you to take attack penalties (similar to Combat Expertise, no larger than your BAB or 5, whichever is less), gaining a number of temporary hit points equal to twice the penalty. The temporary hit points last 1 round, but you can continuously add up to 10 HP that basically “doesn’t count” as damage you take ever round. At low levels, that removes a lot of damage.
Suggestion
Barbarian 1/Pugilist 1/Crusader 2
Heavy armor, a d12 HD and three d10s. Rage and pounce from barbarian, Improved Unarmed Strike, Endurance, and another feat of choice from pugilist, Steely Resolve, Furious Counterstrike, and Indomitable Soul, along with a bunch of maneuvers, from crusader.
For maneuvers, you get five 1st-level maneuvers, a 1st-level stance, and one 2nd-level maneuver. The crusader awkwardly only has only six 1st-level maneuvers to pick from, and leading the attack and vanguard strike are very-nearly identical anyway, so your choices in 1st-level maneuvers don’t matter that much. Anyway, vanguard strike is slightly better than leading the attack, and you don’t need both, so I’ leave out leading the attack and get the other five. For stance, martial spirit and iron guard’s glare pretty much are your best options; the former gives you more healing, while the latter draws attacks towards you by improving allies’ AC without improving yours. The 2nd-level maneuver basically should be mountain hammer, hands down.
For feats, Improved Natural Attack (unarmed strike) and Stone Power are my picks. From pugilist, probably Improved Initiative, since the list is pretty weak; Two-Weapon Fighting or Combat Expertise might be worthwhile if you want to go the TWF route or the tripping route. I’d probably get Superior Unarmed Strike at 6th (unless going for Improved Trip), and Snap Kick (also Tome of Battle) at 9th.
You can enter the class as early as 2nd-level, but doing so is pointless as you have no second class to advance. (Arguably, this could advance one class at double-speed, but that’s a terrible idea even for a high-optimization game.) Thus 3rd is the earliest meaningful level to do it.
This is pretty typical early-entry stuff; there’s a whole handbook on that. I tend to find it pretty hard to read, but it is incredibly thorough.
There are two issues for entry this low:
No class can cast 2nd-level spells so soon without shenanigans
Your maximum skill rank at 2nd level is 5, and mystic theurge requires 6 ranks in two skills
Disclaimer
The following constitutes some fairly high-end optimization tricks. In the case of a mystic theurge, using some tricks is almost necessary, at least if you are to keep up with your single-classed brethren, but these tricks can be used in other cases where they just lead to overpowered characters. For example, easing your way into mystic theurge is one thing, but doing the same to enter dweormerkeeper is game-breaking.
Even in the case of the mystic theurge, though, I recommend that you talk with your DM rather than use these, even if they are not necessarily game-breaking in that case. The mystic theurge is a very weak class, and most, I think, recognize that. If your DM does, or you can convince him, it is far better for the game overall that you work out some alternate entry requirements for that class, rather than set precedent for the use of these tricks. If your DM cannot be convinced of the weakness of the mystic theurge, using one of these tricks is very unlikely to garner you much respect; most likely they’ll just be banned and the DM will be angry at you for trying to slip something like this in.
Spellcasting
There are many ways to get the ability to cast higher-level spells than you should be able to; in most cases these are very limited, or only “effectively” higher level, but they’re good enough for prerequisites, including the mystic theurge.
Precocious Apprentice (Complete Arcane pg. 181) is the easiest, being only a single feat. That gives you 2nd-level spells in any one arcane class. Some argue it needs to be combined with something else to allow you to cast spells as Precocious Apprentice gives you literally one single 2nd-level spell slot which can only cast one spell; personally I think that’s a pretty weak argument (sorcerers only learn a single spell of a given level when they first access it, and I don’t think anyone is barring them). But even so, there are ways to get around that.
That only covers one side, however. It does mean you can do Wizard 1/Cleric 3/Mystic Theurge 10 and only lose 1 level of cleric for 11 levels of wizard, which is solid, but your wizard spellcasting is behind.
The easiest (read: works without relying on variant rules like flaws or elder evils, or on DCFS and similar high-cheese) way to get both is to go with the sha’ir from Dragon Compendium as one of your classes. The sha’ir, weirdly enough, casts both arcane and divine spells. Thus, when you use Precocious Apprentice for sha’ir, you can arguably pick a spell that is available to you as both arcane and divine (Precocious Apprentice requires an arcane casting level, but its benefits don’t mention anything about arcane vs. divine), and your single 2nd-level spell per day can be castable as an arcane spell or as a divine spell, at your option. If that’s a no-go, Alternative Source Spell from Dragon vol. 325 explicitly lets you treat an arcane spell as a divine spell or vice-versa, though it’s got a weird statement about power source that Customer Service read as not allowing you to qualify for mystic theurge. So if that’s out, you can try Mad Faith from Heroes of Horror; if you have moderate depravity, you get a 2nd-level divine spell slot.
So a human (for the bonus feat) sha’ir 1 with Mad Faith and Precocious Apprentice can cast a 2nd-level arcane spell and a 2nd-level divine spell. Take your second level as any arcane or divine spellcasting class, and then your third level can be mystic theurge, advancing that class as arcane or divine as appropriate, and sha’ir as the other since it can benefit from either.
Replacing sha’ir requires a source of additional feats. There are numerous of those, but they get ridiculous fast. And of course, there’s always Pun-pun: it’s possible for a 1st-level character to get all of everything, which is more than sufficient to qualify for mystic theurge (or any other prestige class).
Skills
Skills are trickier, sort of. The typical approach is to acquire the services of a high-level bard and mid-level psion, though there are tricks to avoid the psion (and there may be replacements for the bard). The approach is to have the bard use Inspire Greatness on you, which gives you two more HD than you should have. Your skill rank maximum is now 2 higher than it would otherwise be.
However, Inspire Greatness doesn’t give you an opportunity to gain or assign skill points, which is where the psion comes in. The psion can use psychic reformation to allow you to rearrange your skill points. If you do this while under the effect of Inspire Greatness, you can rearrange your skill points such that you have the necessary 6+ ranks in Knowledges (arcana) and (religion).
The psion can be replaced by anything that lets you assign new skill points (and enough of them to get the ranks you need). Tricks to get new feats could get you Open Mind for 5 skill points. If the bard is undead or warforged or something that doesn’t need sleep, it could just continue playing Inspire Greatness through your level-up from 1st to 2nd. Other possibilities exist.
Then, once psychic reformation (or whatever) is complete, the bard can stop with Inspire Greatness; you will keep your skill ranks where they are. When you level up again, you qualify for mystic theurge and can choose it as your 3rd-level class.
Best Answer
Evangelist is quite obviously designed so you can't get it before lvl 5. For this reason my first advice is: don't do it.
If you really want to do it, here are a few methods, more or less sorted from the most legit one to the worst:
(here start the options I don't recommend)
Use negative templates, like young or Vampire Spawn, Repeatedly Drained so you can take more class levels in parallel.
Have a Bard buddy who inspire greatness on you, so you are considered more HD than you should, and can temporarily get more ranks for example with a headband of mental superiority.
Hope your DM doesn't know about this errata and cheat with retraining to get what you want.
Convince somehow your DM to let you get mythic ranks instead of levels (you can already take templates so it could be possible). Get one level in Magus(Mindblade) and one mythic tier in Archmage. Select Arcane Surge as an Archmage arcana:
Then write some 3rd-level spells into your Magus' spellbook. Due to the way the Mindblade archetype is worded the spellbook feature of the Magus still exists. You don't get 3rd slots but that's not a problem: because of the Arcane Surge wording you only need to know it (and spend a mythic point) to cast it.