I met someone in one of the top 10 US CS PhD programs who got in with no research experience. This person said they focused really really hard on the subject GRE and got a very high score (much higher than mine, and I got into the same program, albeit with some modest undergrad research). So it can be done. A masters with a focus on research as others suggested might be less of a gamble though.
