How can my heroic tier PC contribute more during skill challenges?

Question

My character isn't much use during skill challenges, and the campaign has seen, like, 25% of encounters be skill challenges. I'd like my character to contribute more during skill challenges, whether that's because my character has more skills he's trained in or because he's granting himself or others significant bonuses (i.e. more than +2) or rerolls on skill checks.

Background

Sivart, a human harrier battlemind (Player's Handbook 3 42—4) with the theme vigilante (Dragon #426 26—7) and the background Aglarond (Forgotten Realms Player's Guide 76), possesses Str 10, Dex 12, Con 18, Int 8, Wis 16, and Cha 12, and the feats Harrying Step, Heavy Blade Expertise, and Melee Training (Constitution)—the latter two feats being pretty much taxes and the first feeling like one. His languages are Common, Elven, and Goblin. (Besides Common, two other party members speak Elvish and a third speaks Goblin, so Sivart can relay semi-secret messages.) In short, Sivart's kind of stuck with this class, theme, and background, and those ability scores, feats, and languages. (But see below.)

His trained skills are Bluff, Endurance, Intimidate (the vigilante theme often providing a significant +5 power bonus at level 5 that I don't want to go to waste), and—due to his background—Perception. I like this skill array, but I've found it extremely limited in its applications, making skill challenges more often frustrating than actually challenging.

With Sivart in the mix, the 5-person party is currently trained in every skill except Religion, Streetwise, and Thievery, so being able to make checks competently with those skills is a priority—despite Sivart's ability scores—both during skill challenges and for everyday use. So you know, the party's doubled up on the skills Arcana, Endurance, Insight, and Perception, and tripled up on the skill Intimidate. To be clear, Sivart is the only party member trained in the skill Bluff, so him possessing that skill is kind of a big deal. Also, I'd like to keep Sivart trained in the Perception skill to avoid surprises.

Binds and resources

The campaign's house rules besides those discussed below are irrelevant. (If you're interested, ask in comments.) For example, feat taxes must be paid, and the Fixed Enhancement Bonus rules (Dark Sun Campaign Setting 209–10) are not used.

• The homebrew setting is independent of other settings. All official material is available, regardless of the setting for which it's intended. Setting-specific material'll be reskinned for the homebrew setting. For instance, despite Sivart's background saying that he's from Faerûn, it'd be okay for me to take at level 4 the feat Mark of Warding (Eberron Player's Guide 92)—it'd just be a unique magic tattoo. (Sorry, Mr. Baker!) I can probably convince the DM to allow third-party material from a reputable publisher but probably not outright homebrew material.

• The DM's said that the campaign will likely end when PCs are level 10 but that it could continue afterward. In other words, although Sivart's feats aren't spoken for, I'll likely need one or two feats to firm up my role as the party's lone defender. Assume that the level 4 feat is available; also assume that either the level 6 or the level 8 feat is available.

• I find all the level 1 battlemind daily powers uninteresting, although I suspect that won't matter. I took at level 2 the battlemind utility power feather step (Player's Handbook 3 46) because Sivart's a terrible jumper and swimmer, and those're humiliating ways for an adventurer to die. Still, I'm willing to change that utility power—retraining it upon leveling up—to increase Sivart's ability to contribute during skill challenges. Further, while I'm eyeing greedily the level 6 utility power psionic ambush (48), I'm willing to let that go, too. Assume that the level 1 daily power and both the level 2 and the level 6 utility powers are available. It may be obvious by now, but encounter powers are preferred over daily powers.

• Sivart's three magic items improve only his combat efficacy. The DM—also new to 4e—wants players to submit a wish list of magic items, but I've found that reading 4e magic item descriptions makes me want to drink. Also, I've not DMed 4e so I don't yet understand how treasure's distributed. Answers that also include suggestions for level-appropriate (≤12?) magic items that can help this character during skill challenges are going above and beyond, and that's welcome. (And—sincerely—thank you!) Most common magic items can be straight-up bought in settlements, but gp is at a premium. (At the mo I have but 18 gp.)
• The setting—that's reminiscent of Sword Art Online—allows a character, if in a settlement, to change his build completely for a fee (level squared gp—plus at the DM's discretion the character's magic items also change to better complement the new build). Sivart just did this, though. (He was originally a swordsage.) Nonetheless, it can be done again if what needs changing is the background, languages, or another game element that can't be changed via level-up retraining. (Sivart'd get a loan from the other PCs; this isn't a big deal.) However, I think race is too integral to change, and the vigilante power mark of the vigilante grants an ability that I think is too good to do without—a stance that allows Sivart to mark a foe until the end of Sivart's next turn with each successful ranged or melee attack (including an opportunity attack) that he makes—, but I can be convinced.

An example of what I've considered

At level 4 I could take the feat Skill Training (Player's Handbook 201) or—more palatably—a multiclass feat to get Sivart training in the skill Streetwise and retrain the utility power feather step to the skill power secrets of the city (Dragon #389 36). However, only two of the 7 or so skill challenges so far have occurred in a settlement, and to benefit from that power requires Sivart first succeed on a Streetwise skill check in that settlement. Still, this'll likely be my choice if answers can't offer a better alternative, especially as it allows substituting Streetwise skill checks for Religion skill checks (after the benefit kicks in, anyway), a skill the party otherwise lacks. If this turns out to be the best option, answers that offer optimal ways for this character to gain training in the Streetwise skill are useful. (To be clear, optimal here means seeing the greatest return for the least investment of resources.)

Answer 1

The Things You Have Set

You've covered most of the more specific ways that you can address issues of lower checks at the end (multiclassing being a major way to do so), but I will note that some of the major restrictions you've placed on yourself are probably why your skills are fairly behind. A lot of skill optimization in 4e is about small bonuses adding up across a character (+2 from race, +2 from theme, +1 from an item, that kind of thing), and you've spent most of those options on other things.

Human is a good choice for going broad with skills, because of the additional training, but it is very poor at going tall, since it doesn't actually give a bonus to any skills, as well as not giving a bonus to a secondary ability score.

Themewise, Vigilante is honestly a poor choice for battleminds in my experience, though it is definitely something that has a lot of table variance (I think I've had the bonus to intimidate apply once in 6 levels, but I also play in a plane hopping game where we don't usually stay in a place to be recognized). Meanwhile, I think Mark of the Vigilante is very overblown for a battlemind, since they have extremely poor options for punishing a mark, especially if the enemy have already moved away from you(since they aren't adjacent you won't be able to mind spike or blurred step).

Background is another resource that has some variable value. Seeing that the Aglarond background is on the character tells me that the Forgotten Realms and probably the Scales of War backgrounds are available, so you can use those to boost multiple skills or add more skills to your class skill list. Amn for example would give you +1 Streetwise and Thievery while adding both of them to your class skill list.

Skill Overlap

Generally speaking, I'm not a huge fan of the skills available to Con/Wis. Endurance is Endurance (it's fairly situational but in those situations it tends to be a lifesaver), but my experience with perception and insight is that while it is important to have them in the party, they are almost always passive skills, so being the second highest perception and insight really does often feel like being the first of the losers.

Meanwhile, you have intimidate training, and the only bonus your theme gives is a big but situational bonus to intimidate...which is also the only three person overlap in the party. So your most invested skill, and probably your highest in most situations (given armor check penalty to endurance and the size of vigilante's bonus) is also in competition with two other people. Which can be fun, but it seems like it's been a problem for you. So this marks out 2 of your 4 skills that have a bad form of overlap, leaving you with Bluff (a very good skill) and Endurance (a situational and usually passive skill).

My Recommendation: Focus on Different Skills, Not More

Now, I've looked at Con/Wis battleminds before and never been super overwhelmed but the Wisdom based features, so my recommendation in this situation would probably be to switch over to a Con/Dex setup, and grab the Amn background. Then you can pick up Thievery and Streetwise as skills in place of Perception and Intimidate, and grab a theme like Mercenary (bonus to streetwise and intimidate, and takedown strike lets you prone on OA once an encounter). This lets you keep a decent intimidate, while covering 2 bases the party doesn't have at all.