There are two points here: One, if it was actually possible at the time to get rid of Clause Four (I would personally come down on the side that it was not) and if it had been passed through, then what effect it would have.
The absolute key for Gaitskell was to get as much union support as possible, as the unions dominated Labour Party policy at this stage. Now Gaitskell didn't do that over Clause Four historically - not as much as he should, anyway. He apparently recognised this, and tried with the unilateralism issue to court them. He was defeated all the same. (Albeit that decision was later reversed, but an eventual return to the status quo can hardly be a positive resume, by anyone's definition.) The same went with EEC membership, which Gaitskell was in favour of initially, but eventually opposed, presumably for tactical reasons arising out of his deep problems with the left by that stage as much as anything else.
So the basic outline is grossly unfavourable. Gaitskell was just about able to hold his ground on unilateralism. Just. Now considering that this was a much lesser issue than what many regarded as Labour's soul and basic identity as a party, it seems incredible to suggest that Gaitskell could have overcome all these problems. The party just wasn't going to stand for it back then. There was a reason why no other Labour Party leader touched the issue again for over thirty years, and it wasn't because all (or even most) believed in Clause Four.
Now, just to suppose that it had been revoked, I think it is quite hard to judge what would have happened, but you would certainly have seen massive dissent within the party, and, very likely, breakaway groups. I think it would ultimately have made Labour much less electable, actually, which was precisely what Gaitskell wanted to avoid - a kind of Alliance-Labour split which we saw in the eighties. A lot would depend on what replaced Clause Four.
The actual problem which Gaitskell was addressing was mis-identified by him; the problem was, in electoral terms, not just Clause Four but the entire structure and ethos of the Labour Party as it was pre-Thatcher. Here you had a party mass which was essentially dogmatically Marxist in it's outlook, attached by the vagueries of chance as much as anything else, to a leadership which was, on the whole, pragmatically Social Democratic. It seems incredible that any one man could have overcome all this, certainly not in the fifties, when, let us remember, even the Tories believed in, on the whole, retaining Labour's across-the-board nationalisations. What Gaitskell wanted was, neccessarily, a gradual process of leadership and, more importantly, change in perceptions over the long-term. It was not going to happen in his lifetime.