What exactly is your budget?
There's also the canon 100-400L for around the same (probably a bit more) price as the 300/4 IS and the 400/5.6.
The 400 f/5.6 prime is the sharpest you'll get at this focal length until you move into the huge supertele territory, and very fast focussing. It's a favourite with bird shooters for these reasons. Downsides are it doesn't have IS (though for birds you'll often need fast shutter speeds or be in a hide with support which makes IS superfluous anyway), and it's close focussing distance is very long (3.5m, most of the time this is inconsequential for birds, but trying to get a nice full frame shot of a small bird like a blue tit from a garden hide and feeder setup etc. could throw up problems).
If you're looking to shoot just birds, I'd be looking into the 400 f/5.6 for your purposes
IS should have nothing to do with getting focussed images, all IS does is stabilise and allow you to shoot at slower shutter speeds without camera shake introducing blur. This is only any use on static or barely moving subjects, since moving subjects need fast speeds to eliminate motion blur