To begin, some general advice on the nature of social skill challenges:
First, skill rolls are not, mechanics-wise, a substitute or a parallel system to combat. You as the GM are under no obligation to let the players swap out skill rolls for combat, simply because you're under no obligation to rule that the skill rolls have any meaningful chance of success. It's like a player insisting on making a strength check to lift a two ton boulder-- sure, you can let him make the check for the sake of show, but without some extenuating circumstance, there's no reason to let him succeed even if he rolls a twenty. Some social rolls, like some strength checks, are simply non-starters.
Should they all be non-starters? That's probably too harsh and verges on rail-roading. But allowing infinitely malleable and persuadable and deceiveable NPCs is also problematic.
Second, even if you decide that a certain situation is amenable to this treatment, you are under no obligation to have it resolve in just one roll. The 4e notion of the skill challenge is a highly useful model, even if the math needs to be adjusted somewhat for the situation. There, the core idea is that multiple rolls, preferably used against multiple skills in concert, are necessary to achieve large results.
Third, related to this, you are under no obligation to allow the player to control the pacing of this kind of extended skill challenge. As the GM, you are in control of the pacing, and if you decide that it would take several lengthy units of time (either in-game time several days, or RPG-time of several sessions) to accomplish this goal, that is your prerogative. I would try not to be arbitrary about it, but it is in your hands.
Fourth and finally, you are under no obligation to treat this as a binary pass/fail where the players either succeed and have a new band of minions, or fail and have no consequences. It should be possible, for instance, for the players to screw up so badly they are even worse off than before (somehow) or for a partial success to occur, or for something weird and unforeseen (relatively speaking) to happen that no one planned on.
To continue, some concrete suggestions for this encounter:
Disclaimer: I've never had my players try to take over a band like this, but I have had them on numerous occasions try to influence a large number of people, and I have used the skill challenge motif, and I have this advice to give:
First, even if it takes you a few minutes to settle your mind, make some notes about how many successes and failures are necessary before the outcome is decided, and what sorts of skills are helpful. I wouldn't treat that as etched in stone (especially if the players have a creative idea) but I have found it helps keep me objective, and prevents me from falling into an overly adversarial role.
Second, if you are going the extended skill challenge road, it is critical to give your players feedback about whether they are doing well or not. My early failures in this regard happened because I knew the players needed (say) four successes, and had achieved three, but I failed to communicate a sense of success or progress, so they gave up.
Third, it sometimes helps to personalize this sort of thing by casting it as a two sided conflict: The PCs, say, vs the Redbrands' leader and top lieutenants, where the prize is the course of action or the loyalty of the rest of the group. This increases the drama (the opponent has a face) but also gives a lot more scope for reactions, role-playing, and understanding why the group is not amenable to persuasion. (Say, because Lieutenant Thuggy McThuggerson pointedly reminds everyone what happened the last time someone tried to tell Captain Brute what to do-- that would be the existing leaders' own intimidation or persuasion roll.)
Fourth, on the idea of non-binary results, consider carefully what a total catastrophe might look like, or what a partial success might look like. Are the thugs so regionally scary that they could put a bounty on the PCs' heads? Could the PCs peel off a quarter or a third of them and start a gang war? Could the local authorities exploit that? Complexity is the friend of the GM.