I was in the same boat as you until recently. I chose the 400mmf/5.6L lens and I could not be any happier (well maybe if I had the 600f4L.....). Granted, the 100-400 has IS but in testing the lenses head to head at the store I found that for any shots faster than 1/500sec, the 400mm prime was sharper than the 100-400.
after I bought it, I have shot it at 1/250 sec handheld with acceptable results. if I'm shooting still objects... I put it on a tripod anyway.