It is very possible to do NS in the military. The Army, in particular, is hurting for neurosurgeons and if you knew what I know, you'd know how badly they want to keep their NS numbers up.
As far as I know, however, there are only a couple of spots available for training. But they haven't been as competitive as some other surgical subspecialties. So if your scores are good and you love working on spines, it's a very available route. As far as General Surgery followed by Neurosurgery....I can't say I've actually even googled this, but I'm pretty sure that's not an option in the US. Might be I'm wrong and there's some off the wall program out there that offers it, but if you did it in the Army, you would probably owe somewhere around 40 years.