It would be helpful to know what your budget is, since there's a considerable difference in cost between your cheapest and most expensive solutions.
To answer your original question, I used to own the 70-300 non-L, and while it was good up to about 250 mm, I found mine to be soft after that, to the point of being unusable. I eventually sold it and kept my 55-250 instead, which was (and still is) good throughout the range. If you think you'll be shooting mainly above 250 mm, I would not recommend the 70-300 non-L.
I still own (although am selling) a 70-200 f4 IS, and it's an outstanding lens in every respect. For a lens in this focal range, I'd definitely recommend going with IS if you can; it makes a huge difference in poor light. I used to own a f2.8 non-IS version of the lens, but sold it for two reasons: weight (the f2.8 lenses are huge) and lack of IS. My keeper rate, even in low light, improved considerably when I bought the f4 IS instead. And, as an aside, I liked the smaller, much lighter format better. If you haven't considered the size and weight difference, you might want to do so. It doesn't bother some people, but it did bother me.
I now own the 70-300L, and consider it to be the best of the bunch. It's a fantastic lens, smaller and lighter than the f2.8s and equal in sharpness and performance to the f4 IS. That extra 100 mm is extremely useful. I bought mine used - hence my question about your budget. They can be found for around the same price as the Tamron 70-200 VC. And if you're thinking of spending in the region of $1000, then a used 100-400 L isn't out of the question either.