How do I convert a 3-way circuit with two lights into two 3-way circuits that control each light separately?
First of all: You will absolutely have to pull new wires for this, and it will involve opening the drywall in several places. 

You'll also have to patch the drywall after, and almost certainly repaint each wall you put a hole into. You may be able to get away with painting just a section of the ceiling without it being noticeable, but very rarely can you get away with it on a wall.



Current wiring

What you have now is one of these two wiring variants:





Necessary Changes

You essentially need two separate 3-way circuits (take a look here for different wiring variants: http://www.buildmyowncabin.com/electrical/wire-3-way-switches.html). 


In variant #1, you'd have to pull a new 14/2 between each light and switch, and change the wiring at each light. 
In variant #2, You'd need a new 14/2 between the two switches, and another 14/2 between the switch and first light or to replace the current 14/2 with a 14/3. 


Making diagrams for these is not simple, so if you describe or draw your current wiring diagram (or at least post pictures of the wires inside each box) then maybe I can provide some more concrete instructions.