starting level one, and all books. I dunno what the rest of the party is doing. however, I only have player's handbook, complete arcane, complete adventurer, dragon magic, spell compendium, monster manual and monster manual 2.
I'd find out what the rest of the party is doing. The powerful trick to gestalt is to find a way to gain extra actions because economy of actions is what limits the character most. Factotum is the class that does that. Ruby Knight Windicator is the prestige class that does that to some degree.
The other, less powerful trick to gestalt is to pick a class with passive abilities like dragon shaman, marshal, and warlock. Having your abilities always on regardless of action is great.
If you play a Paladin, Battle Blessing is the must have feat. However, that's Eberon (actually it's not, it's Complete Champion!). Of the books you have listed, You could pull off a very nice cleric//warlock who rocks the passive warlock abilities. Just re-flavor it as a Paladin and go to town with an eldrich glaive (dragon magic). The most important book you are missing for any gish gestalt build is Complete Champion, which was one of the last and best books in 3.5.