First of all, you can do anything in tabletop RPG you can imagine. And if you do it right, most things can be fun.
But before I get into that let me say that 4e style skill challenges is a terrible idea in most cases.
To understand why, let's just look at a very basic level how a PnP RPG works.
In general you have one or more players and one special player, the referee or game master who sets the stage or frames the scene. Players propose actions for their characters to attempt based on an understanding explicit or otherwise of the stakes, and then the results are randomized based on a fortune mechanic and the game master on the basis of the results of the player's fortune narrates an outcome or resolution that changes the scene or possibly leads to a new scene.
The exact system can very in a variaty of interesting ways. You can have explicit or implicit stakes. You can have a fortune that precedes the narration of the proposed action, or the narrated action can come before the fortune. You can have different sorts of fortune mechanics, and you can have the players take a role in narrating the outcome. But in overview, that's how a good PnP RPG works.
The problem with 4e style skill challenges are many. First, they abstract away any relationship between the players proposition and the outcome, so that it doesn't really matter what the player proposes the outcome is purely based on fortune. This is about as interesting as the card game 'war'. It reduces the system to something that barely takes any player input. Secondly, they propose a system where by the fortune - the odds of success - radically doesn't depend on the actions being undertaken but on an arbitrary generic structure with totally broken math. Thirdly, it substitutes the above organic evolving mutually creative process for a fixed framework. Fourthly, it produces a system that isn't 'cinematic' in the sense that doing normal process simulation like the above just naturally creates a story with many branching points and concrete scenes. You don't have to work to make it a story, it just becomes one. You either leapt over the pit, or you fell into it. Either outcome creates a visual impression in the imagination. Either outcome strongly encourages all participants to share in the imagined scene. A 4e skill challange just encourages participants to share in the really dull game system it is defined by.
That isn't to say you couldn't occassionally have a skill challenge that made sense, but that it would work very differently that 4e's skill challenge does by default. An example I've actually ran in a game back in 1992 before 3e was even a remote reality much less 4e, was an impromptu arm wrestling match between a PC and an NPC that fundamentally amounted to "gain 3 successes before the opponnent does". I adopted that because it seemed natural that an arm wrestling match worked that way, and made it obvious where the arms of the participants were. So yes, sometimes you'll need a skill challenge like mechanic, but most of the time it will just get in the way and destroy your game and the fun.
Don't try to create a generic system for resolving problems. Complex interrelating skill checks will evolve on their own if you just create complicated situations. Suppose for example you set a scene where its in the players benefit to get at least 5 of a cities 9 Aldermen to support the PC's in some initiative. This is a skill challenge in a sense, but its a wide open one. It could be resolved with something as simple as making conversation and 5 successful diplomacy roles. Or, it could be that each Alderman has a different set of conditions to persuade them - some are hard to persaude by diplomacy, but perhaps can be persuaded by blackmail, or bribery, or intimidation, or simply by successfully using Charm Person. Maybe some want to make bargains with the PC's, offering the vote in exchange for some service the PC's can provide - fetching a dingus, killing a foe, rescueing their daughter, etc. Maybe the PC's are in position to assassinate one and have him replaced. Different approaches will have different outcomes and repercussions and chances of success but either way you've got story naturally being created as a result of the play, and not added to a static system as an afterthought.
Ok, so things that I know you can do in an PnP RPG that are fun:
1) Have a Chase Scene: This is something like a skill challenge, in that it generally involves at a fundamental level getting more successes than failures over a time period, but its not really tightly structured like that. Also, keep them fairly short if you can, because dice rolling without signfiicant changes of scene is boring. Instead, think of the sort of things you've seen happen in a Holiwood chase scene and string together a series of mini-challenges. "The bad guys are getting away with the loot in a wagon, we've got to chase them.", creates a natural chase seen. "The assassin is on the roof!", creates another one. So does, "The monster is atop the princess's carriage" or conversely, "We're riding shotgun on the princess's carriage when its attacked by the dark overlord's elite cavalry!"
2) Investigate a Mystery: The classic non-combat challenge. Find the breadcrumb trail that leads you to be able to open up a door, pass judgement on who is the enemy, and find the missing whatsit. Remember as the game master to follow the 'three clue rule'.
3) Compete in a contest: Arm wrestling, chariot racing, gladiatorial combat where putting on a good show is as important as winning, aerobatic pegasi contest,
4) Get to know NPCs: A lot of the joy of a good PnP RPG is thespian. Being in character, exploring your character, in relationships with colorful NPC foils, rivals, friends, enemies, paramours, servants and leiges with their own quirks and agendas.
5) Help a poor widow maintain her farm: Again, this is something like a skill challenge, but its not got an arbitrary format. It's more like, "Tend the animals", "Harvest the crop", "Weed the vegetable garden, but don't get bit by the rattlesnake.", "Get rid of the moles.", "Remove the wasp nest from the outhouse.", and "kill the giant rat under the hen coop" Combat, spells, skill use, and simple hard work resolves the problem. Situations like this where you resolve ordinary problems are great at low levels, for small children, and as changes of pace. Tailor things like this to the players interests. Some players want to 'make a difference'. Others just want 'phenomal cosmic power'. Players that want to 'make a difference' don't always just enjoy killing bad guys in ways that seem barely different than robbery and murder of guys with black hats.
6) Explore the world: Much of the joy of an RPG is finding surprising, clever, complicated and wonderful things that the GM has put into his game that makes it seem alive and real.
7) Survive Hardships: One game I wouldn't mind running would start with a shipwreck, and the PC's being the sole survivors stranded on a remote island with basically no equipment. Figuring out where to find water, food, shelter, and ultimately tools and weapons would I think make a great low level campaign. One thing I'd love about it is just how important any Craft skill you had would be. Just getting a good night's sleep would be a challenge at first.
8) Mass Combat: Run a large battle using a mass combat system of some sort, with the players 'commanding' the troops. This is another sort of sitaution where you want and abstract system rather than trying to apply the normal skirmish rules to 10,000 fighting individuals, but where you don't want anything like a 4e skill challenge because the system that works is one that is tactical, positional, and visual. You want the players to be able to see the charge of the cavalry, the flank being overwhelmed, and so forth. You don't want to be narrating a thin tacked on story layer to the sytem as an after thought. You want the system to actively create the story.
9) Figure out puzzles, or answer riddles: Sometimes its fun to make the skill challenge actually challenge the players rather than the characters. Ideally these should be fairly short and involve every player able to contribute ideas. Mazes are bad ideas (they take too long to be interesting) and chess probably is as well (only one player is really playing). But there are plenty of little puzzles you can put into your game organically (repair a derelict ship to keep it from sinking, bypass a trap) or inorganically (a riddling door, a puzzle to open a treasure box). If you know your players are particularly good at something, put that in the game.
