Factotum?

[Srasy]

I am starting a DND group and most of the people are new to the game so I will be making their starting characters...
So I asked everyone what they like playing and I have done what I think is a good job in making their characters.
The problem is that I don't know how to make a charismatic skill monkey/combatant/ who can cast spells that will be competitive at lvls 4-8

My first thought was Factotum but it really doesn't get going from what I have seen tell lvl 8 which will be around the end of the campaign probably (A tripping build doesn't really get good AC because you need str int con and cha if you dip marshal also there are lots of other melee characters and a archery build doesn't really get good tell 8...)

Rogue might be interesting but doesn't really have much to do but sneak attack and social stuff and frankly I think it is a bad class

Beguiler might be interesting but our wizard is specializing in Enchantment and I don't want to steal anyone's thunder...

What would class and build do you think would be good?
Also do you have any other Ideas to help the party Mainly the paladin because the only thing I see that's cool is the mount and I think ubermount would be a little to OP?

Party Composition
Paladin of courage who will be getting a dire wolf at lvl 6
feats nymphs kiss, animal devotion or Divine shield (probably devotion at 4 then shield at 6)

Barbarian/Ranger Frostblood Orc

Druid who will take natural spell at lvl 6...

Druid who will go into elemental archon and will trade away wildshape to turn get the thing that allows him to turn into fire and will also get and fire elemental companion and 3 fire mephits (semi experienced 3.0 player but we are playing 3.5)

Wizard specialist enchantment (Experienced player though I question his choice of school)

[Wise Green Bean]

Beguiler would be best for a spellcasting skill monkey. Spellthief is an ok choice. A level or three of factotum plus wizard stuff would make a decent gish. He has some good skills and if you take three levels, he'll be quite a good gish. Maybe an abjurer for moving on to initiate of seven veils or abjurant champion or something.

[TiaC]

What about Bard or Bardblade? A well-made bard seems exactly like what you want here.

[Draz74]

Rogue can be made to work pretty well if you know what you're doing -- and the big #1 trick is the Penetrating Strike ACF from Dungeonscape (or the slightly better but much more obscure version of it, from Expedition to Castle Ravenloft). If you take that, most of the big problems with Sneak Attack go away, and all you've lost is Trap Sense (meh).

Likewise, Factotum is certainly not a terrible option; I particularly like using it to make an archer with Knowledge Devotion (especially if Flaws are acceptable, since archers are always feat-starved).

But your best option might be a multiclass amalgam. My build that tries to emulate "the classic Rogue" as much as possible, for example, goes

Rogue 1-4 / Swordsage 1 / Factotum 1-2 / Swordsage 2 / Factotum 3 / Uncanny Trickster 1

... for the first 10 levels. Admittedly, this isn't a Charisma-focused path. So you might be better off with a dips in things like Marshal and/or Binder instead.