How can I get recessed lighting on a middle floor?
There's two main parts to it:  


Long flexible drill bits. Home Depot and Lowes sell them.
Cut access holes as needed and patch them afterwards. Since you're installing recessed lights, I would think the holes for the lights should give you enough access most of the time. 


Some (most?) flex drill bits allow you to remove the bit from the drill (after the end of the bit gets where its supposed to go) and attach a wire to it and use it to pull the wire through. Such as this:  

http://tessco.com/products/displayProducts.do?bgCategoryId=558922

Another option is if you want to drill into the skipped joist bay from both sides (the existing light and the new light). I could imagine shaping two coat hangers (or similar bendable but stiff wire) into shapes where one could hook the other in the skipped bay and then pull it and an attached pull string through. A combination of a hook and loop perhaps.

You should think about the size and location of the holes you will drill in the joists. A larger hole will make wire pulling easier but reduces the strength of the joists more. There are rough guidelines/rules of thumbs.

http://www.electrical-contractor.net/forums/ubbthreads.php/topics/196140/Drilling_a_floor_joist.html