What other constitutional qualifications are there?
Your parents have to be citizens at the time of your birth for many years. That is the major problem people have with Obama. His father was not born in America. This will never go away if Republicans start ignoring constitutional requirements.
There have been numerous threads on Free Republic about how “natural born citizen” is defined.
And those threads, some quite lengthy, are full of controversy as to what “natural born citizen” really means. Apparently the courts have never given a definitive ruling. In Obama’s case, his being born in Hawaii seems to be all that matters, not who his parents were or their citizenship status.
Realistically, perhaps not within the legal framework you are suggesting, but realistically, nothing is going to be done if Rubio was a VP running mate, or if he ever runs for president in the future. Realistically, nobody is going to stop someone from running for office based on the natural born citizen status.