Even if we restrict the definition of "science" to your definition; that is that science is purely "evidence-based, hypothesis-driven testing", computer science would still fit the bill.
Remember, that CS is as diverse a field as modern physics is. You have theoretical CS, where you tackle questions like: "What is a good, logical definition for computability?" or "How can you logically prove that a program terminates/runs in X time/consumes X resources, no matter the input". This is fully equivalent to the questions of theoretical physics, where you tackle the Grand Unified Theory -- joining gravity, the weak and strong force as well es electromagnetism.
These theoretical question can be brought up without need of evidence -- if all you're interested in is disproving something. According to your definition, this means that the theoretical aspects of both physics and CS are not "science". Okay, let's run with that.
The nice aspect of theoretical questions that can't be disproven by pure thought is, that they lead us on to try to discover concrete evidence that a given theory is true or false in real application! And this is where your rather narrow definition of science comes in, and the point where we find that both practical physics and practical CS fulfill the criteria.
For example in physics, we can test the theory of relativity by building telescopes that look at stars and black holes, to see whether the hypothesis' predictions hold true to raise the hypothesis to the state of a theory. As can be seen with the term people use for "X of relativity", this has happened for relativity.
But if you look with even more than a superficial glance at CS, you will see that the same process is at work in moving from theoretical CS to practical CS. One open question of theoretical CS is whether P = NP or not [1]. So far, we are incapable of disproving either possibility with pure thought. Thus, we turn to practical CS where people try to find evidence of either in the real world. After all, if you can create a program on a real computer that solves an NP-hard problem while never leaving the limits of P, you have conclusively shown that P = NP. So far, we've only found approximative or heuristic solutions that do that, so after 50 years of turning up with "no evidence" we are allowing ourselves to say that the hypothesis of "P != NP" should be treated (even if only cautiously) as a theory -- and we're indeed doing that, as you can see if you look at most modern encryption methods.
But you might say: That is not enough! After all, you could reduce any written computer program on a physical hardware to a sequence of logical steps in a system modeled with pure-thought. And indeed you can, as the Turing-Model of computation promises exactly that -- and so far physical evidence agrees with us. But isn't the same true for physics? After all, physicists search for such a description, too! It's what Maxwell-Clark, Einstein and lots of other physicist were and are after when they ultimately search(ed) for the Grand Unified Theory. How can you blame CS for already having found its Unified Theory?
But the last example finally puts the nail in you view: What about Quantum Computers? They are the point where physics and CS meet; both on the theoretical part (Quantum Theory / Quantum Computation) as well as the practical part (building the thing and proving that the shit actually works as advertised).
So, if we accept your definition of science; then it follows directly that if CS is not a science, Physics can't be either.
[1] - http://en.wikipedia.org/wiki/P_versus_NP_problem