It's totally possible. Even in a book with only one main plot line, there's no need to write the scenes in order. This is one of the chief benefits of writing a good outline before you start writing - you know from the start what the scenes are and how they fit together, so if you want to write the funny scenes when you're in a good mood and the sad scenes when you feel like a good cry, you can!
What you will need, though, is a willingness to put the work in to integrating the scenes properly when it's time to put the novel together. You may have already worked it out at the outline stage, but if you didn't, you'll now need to pay attention to the way the scenes work with those they're being put next too. If you have ten pages of down-time with one plot, you should probably avoid matching that to another slow spot of the other story.
At the same time, you don't want the tones to totally clash with each other. (eg. don't go from a a super-sad story to a silly, irreverent scene unless you're really good and can actually pull it off). You'll also need to make sure that readers are discovering things at the best time for both story lines, and that you're maximizing the impact of the way your stories are parallel (like having one storyline discover item A at the same time the other story line is discovering the importance of item A).
Personal Experience: I write Romance, usually from both character's POV, and I sometimes write all of one character's POV and then go back and mix the other character's chapters in. This isn't quite the same as your situation, obviously, since my characters are interacting, but for what it's worth...
I find the advantage of doing it this way is that I'm able to really get inside the first character's head. It's easy to have him or her act as if s/he has no knowledge of the other character's perspective, because I barely have that knowledge myself. And I can keep the thread of emotion running, uninterrupted.
The disadvantage, or at least the thing to be aware of, is that the second character tends to get treated as secondary, even if the outline made it look like that character got equal time and attention. I have to really work to ensure that I'm not just having that character react to the first character, when I really want him/her to be living an independent life with independent goals and motivations that just happen to intersect with the first character. This might not apply if your characters don't really interact.
Good luck with it.