ok then, enough talking, looks i am going to have to try it myself. I'll go for extra challenge - no pet dragon use. But first off i'll finish my amusing no loss mage game which I called "crazy phantom" using high intelect with griffins, demonologists, royal thorns (with lots of fire res.) + paladins. No needn for fifth unit.

Right, i guess i try my luck with mage. yes, low leadership will be an issue, but i remember starting once with two officer batons in debir. I do not think it is considered cheating so i reload several times to see. we'll take it from there. I never was into trapping, but in this harsh challenge it seems as a way to go.
Keep you posted

Before we start let's clarify the rules of the ultimate challenge again:
1) impossible difficulty
2) hero class: any. Mage has the harshest start due to low leadership, so I chose mage for extra challenge. Choice is yours.
3) no loss. You can lose summoned crits at your will, but original army has to be at full numbers at the end of the battle.
4) no usage of any 5th level units throughout the game in your army
5) no wanderer scrolls to be used throughout the game. All they're good for is 5000 coins when you sell them.
6) no pet dragon usage at all. He stays at zero experience untill the end of the game
7) no map kitting. You can move the creatures at your will to get treasures, rods from behind them, but never pick new continent scroll without proper fight.

Here is my progress.
Currently 42 fights done. restarted Debir few times to get favorable conditions. Found officer batton,trap scroll,bought stone skin, started working on trap and guardian medals immediatelly. Found Bolo & Scarlet island scrolls. Finished temple of hope quest, got paladins, archmagi. Split archmagi in two groups for long time, it incredibly speeds up going for medals. After my 42 fights I have trapper III medal - average of more than 2,5trap per battle and guardian II - 290. Cleared Debir easily. Cleared Scarlet apart from presumably Verona scroll, and Norbu. Got Rusty anchor scroll, it's getting interesting:-). Currently clearing Bolo, mostly done. It is getting tough. My line-up: archmagi, snakes (got the boots), paladins, inquisitors, royal thorns. Considering employing droid combo or even two groups of droid archers for nearly suicidal trips under magic shield and then quicky retreating for repair with other group. Was hoping for Evil beholders somewhere for crowd control, but no luck. Got I point in concentration, transmute for steady mana inflow. Cannot decide whether to go for higher magic or increase distortion & fire, have mana only 39. Bought ring of mind class 2 for 20000 with tears in my eyes:-). Got 20000+coins, so so far so good

Without the dragon, the Warrior is likely the hardest, not the mage.

yes, warrior might be overall the hardest, but i was talking about the beginning of the game - mage has the hardest time. I wanted to see if it possible to do what i wanted right from the start.

travel update:-)
fights done - 74,level 15. Cleared everything on debir,scarlet,bolo, left just zig-zag,annoying pirates and another continent scroll on rusty and went for fight for Verona scroll. Boy, i miss that dragon. If he could only just kick opponents back 1 tile, it would be helpful. Made it to Verona,picked everything,got royal griffins, no archmagi or demonologists though yet,but utter disappointnment with spells. NO target, no phantom so far,two crucial spells! Hope i won't have to restart, fights are getting extremely tough, and due to just one lot of res coming from 22 paladins and 48 inquisitors, i have to be very careful. droid combo was helpful against ground troops + few shooters,when shooters fell under fire rain, otherwise unusable. got trapper, guardian 3, working on fire mage. Traps are crucial, cannot imagine it without them. Many fights won by heavily employing fear spell. Still do not know which route to take, so saving runes - have 15-19 of each ready. Statistics are lousy - a:3,d:2, i:14, leadership 5000. Relatively lots of money - 60000+, but i was not buying any artifacts really. Can be done so far without dragon digging,see mr. dobrev? :-)

I have to agree with Temjingold, warrior is the hardest specifically for this challenge since you don't get to use your pet dragon. Their vaunted extra leadership does not come into play up until the early middle of the game. At the early levels, the paladin could easily outpace them with regards to leadership because he could pump Glory to level 3 the fastest.

I might even go so far as to say that mage has the easiest for this challenge. This is because you simply have to wait for your mana to go back to max, then fight the next battle at full magical power. That is why in my suggested challenge I placed the time factor of 7 days. Without the time factor you just always wait for your mana to regenerate to max, and run around picking up the free gold/chests/banners, buying the best lineup, and then start killing enemies in the order of weakest to strongest.

If you are looking for favorable starts, mage definitely has the easiest time. If you start with an Ancient Amulet, you can seriously just nuke everything from the get-go with no need for an army. The warrior has no form of control w/o the dragon and no way of keeping the enemy from her army.

c'mon guys, i started with mage, having no idea what is going to be like without dragon and kitting, wondering if it can be done at all. Once i finish the game with mage, i try warrior.
now in montero, breathing bit more easily, wondering what is going to like later without lightning ball.

Understood, I had no intention on my initial post on raining on your parade. The conditions that you set are definitely a challenge, no matter what class you use.

So the droids did not hold up? I guess without archmage magic shield they lose a bit of their tanking power. But even with just level 1 Stoneskin their physical resistance jump up to 40%. And so long as they have 1 unit left all they need is time to get back up to full health, even if you have zero mana/rage.

Perhaps you could look into using ghosts/cursed ghosts. Even without archmage (that you mentioned you have yet to find) a level 1 Stoneskin would give them 70% physical resistance. The only restriction they have is that you need at least I think 21 ghosts/13 cursed ghosts to be able to self-resurrect their numbers via their soul drain ability (I believe they use 25% of the damage they deal to self-resurrect their numbers), and this minimum number is achieved by leadership 2,000+, and you already have 5,000 leadership. Your paladins and inquisitors also don't mind having them tag along.

regarding previous post about starting with ancient amulet.
I seriously doubt amulet can spawn in treasures in first 3-4 islands, Verona onwards maybe? So you'd have to buy it, that's 50000. Don't forget you do not have dragon for digging. Until i reached verona i only bought officer baton, snake boots (very important), sone skon scroll and some magic ring. Did not have more than 40000 until Verona, so ancient amulet would be affordable alone after clearing maybe 3 islands.
Druid combo. Maybe my comment on them was a bit harsh, I used them for armies consisting of mainly walkers, then discovered good old setup eventhough weaker (original just 4 r.thorns, 5 archmagi, max snakes,paladins,inquisitors) worked, so i did not look back. traps + fear spell + favorable battlefield setup were the key. Sometimes i had to lure the enemy all around the map in order to find good setup:-)
Btw. since we playing without 5th level creatures, guess what i found right in the beginning in debir castle. -20% req. for red dragons:-)

Once again about druid archers combo described earlier. I think it will be used with warrior,not mage. By splitting druids, you're losing 1 slot, you're bound to take 5 archmagi with you for shielding, so that leaves only 2 slots for other units which should demolish enemy's army while he is busy with droids. But what you're going to take so early in the game? Paladins with limited range and weak inquisitors or vulnerable snakes? As mage you're have spells, but very weak ones around level 10.

Travel update.
Fights 110, level 24, a:10,d:15, i:32. After reaching Verona, finding no target or phantom it became a bit desperate. I killed few manageable armies and concentrated at all costs on getting to Montero. Done it. Found phantom, some nice goodies, but no target, time back, geyser, death star. Just picked freebies there and went back to Verona. Smooth sailing now, killing even map guardians there opening elon,tekron. Money 300000+, should not be a problem until end of game, this proves you're can get away without dragon digging. New problem beginning to appear - very high number of enemy units, which under normal circumstances get targeted by lightning ball. Strategy is fire arrow, poison, slow, plague maybe pygmy in order to bring the numbers down before they reach you. Good old fear spells works wonders. Considering dropping inquisitors as a last level 3 unit, having all level 4, for efficient fear. Suprisingly, kept snakes up until now. Their initiative 7 gave me 2 attacks, no retal., lovely poison with Alchemy medal 3. How about snake distant attack over trap? Aparat from brutal damaging spells like death star, i always preffered "biting" spells. Even late in game I was casting flame arrows for guaranteed burning high numbers for 3 turns. I think at this point i can say game might be beatable with mage, since in boss fights i won't be to use dragon anyway.
Can't wait to try warrior