Beyond the obvious in rules options of spending feats for skills or using classes that already have access to these skills I would probably run more of the stealth checks as skill challenges. Of course the skill challenge approach could be used with no rule changes at all
so some other ideas include...
Rework the class skill lists to make Stealth more available to all classes. These characters are special. Perhaps they are part of a kingdom's SEAL training and do not fit the normal character class mold.
How about another approach where the "leader" could inspire others to be more stealthy. As a warlord inspires others in combat perhaps the rogue could have a power to make the group a bit more stealthy/acrobatic? Or trade out some of the warlord powers to enhance the skills you mention. Consider this your SEAL team leader. Hmm... a rogue like leader. Might be something to that.
Final thought I had is perhaps something along the lines of the old teamwork feats. I never played with them, but as l recall there was one about climbing in a prior edition. Might be worth looking up to see if that inspires you.
Just some random ideas. Hope this helps.