MCAT and GPA both play a huge part in their decision. However, it's not the only thing. They also look at your activities and honors/recognition. The school you go to for undergrad may play a role if you come a well-known school.
I had a 3.66 GPA and a 27 on my MCAT (
). My recruiter said very few people get the Air Force HPSP with a 27. But he believed that I seemed to have made up for it with my relatively "high" GPA and that my school was well known enough. I also had an acceptance into a med school.
With the Army and Navy, the numbers may be a little lower. Overall, who knows what will happen unless you try because they look at everything.