Non-science major the first time around? First you have figure out how long it will take you to get that second degree. If it's more than two years including summers, I say don't do it. Furthermore, if you have to take tons of useless core courses, do not do a second degree. I am getting a second degree... because it works out that I only have to take 1 useless class - the rest will be in the sciences or English prereqs. I was a non-science major so since I'd be taking all of these classes in a post-bac anyway, in the same time frame, why not get a science degree out of it? But you can only find out transfer credits with an audit of your existing classes. Some schools will do this before you even apply. IMHO, it's worth at least checking out.
If you were a science major, or didn't like the above option, consider one of those programs where you take classes with first-year medical students, but you're a post-bac. Since in this scenerio, you've bombed both the overall and the science GPA, you need to show that you can kill specific med school classes.
And as you already know, crush the MCAT.