They released 3D glasses technology quite a long time back for the PC, and actually, I think someone released one that's supposed to work with consoles. But the headache problem you mentioned is indeed one of the primary drawbacks of the technology. How it works is by calculating the proper 2-dimensional skew to apply to 3D images to make them properly pop out. In essence, the overall framerate is halved because of the need to double the frames to be shown, one for each eye. There is an eyeglass peripheral that is synced up with the framerate to cover one eye at a time, depending on which eye is supposed to see the current displayed frame. I think the technology has somewhat improved over the years, but it still doesn't work perfectly. I don't see how these sorts of systems currently advertised for consoles could work, since there is no way to program a console to do all the necessary calculations without it already being coded in the software.
Long story short: yes it's possible, and its already been done.
There is another possibility. Each color has an inherent warm or cool property. Warm colors, like yellows and reds, move into the foreground, and cool colors, like blue and purple, move into the background. I'm sure you've had experience with those 3D glasses with clear lenses (vs red/blue ones) that make this possible. Also, if you have messed up (or super-powered?) eyes like I do, you can also experience this effect with no additional aid (I often see the different colored writing on the boards at school hovering on different planes). The benefit of this is that images won't have to be generated in headache-inducing red & blue psychidelia. However, the downside is the amount of planning time to produce a properly functioning image. I originally thought that Spy Kids 3D would be done in this way because red/blue 3D glasses technology is so archaic, but upon deeper analysis of the trailer, I was confused as to why a character wearing purple would be in the foreground while a character wearing red would be in the background. Turns out I was wrong.