Same boat here. I have a 70-200/4L non-IS and think I could get pretty good use out of something longer. I tell you what, as a recent Canon convert (June 2010) it sure is nice to have so many GOOD options. Nikon's 80-400 really isn't that great optically and also focuses slowly, their latest 300/4 still doesn't have IS, and they have no lower cost 400mm prime option, just an enormously expensive 2.8. With Canon, the 300/4L IS, the 400/5.6L, and the 100-400L are all strong contenders and it's tough to decide.
On the 400/5.6L, I agree that the lack of IS on this lens really makes it a good light lens only, unless you're OK with walking around with at least a good monopod all the time. Optically I'm sure it's the very best lens out of the three at 400mm, but by far the hardest to get good results from. Don't think it'd be the best option for me, so that narrows it down to the other two.
On the 300mm f/4L IS, having a relatively large aperture available at 300mm is enormously appealing, both for speed/action shots, and the potential to yank backgrounds a bit more out of focus. Was planning to eventually get a 1.4x extender also, so that would make it a stabilized 420mm f/5.6.
The versatility of the 100-400L is enormously appealing to me though, being able to get near and far and wide and super long shots very quickly. For landscape shots, I might have some super interesting light but only for a few seconds. Can quickly dial up whatever FL I need and get a few shots off, rather than having to switch lenses or yank an extender on or off. Can see it being quite useful for airshows, random aircraft or helicopters flying by the house, the aforementioned landscape stuff, and although I know it's not idea for it but outdoor kid sports also. I have enough ISO headroom on the 5DmkII that the slower speed of the lens in most outdoor conditions shouldn't be an issue for that.
So we'll see I guess. Right now I'm leaning towards the 100-400L, but I don't have the money yet and could change my mind before then. I've also wanted a 135/2L which is in the same general price range as these lenses, but I already have the 70-200/4 that covers the same range and a Nikkor 135/2.8 AIS that I can use with an adapter. Am not into hyper-thin DOF stuff either, so I'm thinking one of these super long lenses would be a better choice, and give me something that I don't currently have and could arguably use a bit better with my current system.
Edit: I see that the 100-400 rents very cheaply from LensRentals.com, so I'll probably just rent it for a week to see how I like it. Have rented from them before and have always been very pleased with the service.