How can I install a ceiling fan, recessed lights, and receptacles on the same circuit?
If you can run a new power line to one of the outlets, it may be an easy way to re-use the rest of the existing wiring without having to break walls open too much (less than if you run a new wire from the switch to the ceiling boxes). 

The feed would essentially come from the outlets, to the switch, then to the lights/fan, and the existing feed would no longer be used.



You might need to cut an access hole below one of the outlets and then fish a line from underneath, or cut a hole on the wall opposite the outlet, or if you're really lucky, one backs onto an unfinished space. It's very hard to say without actually being there. 

Some tips:


Try to avoid opening exterior walls, as they have insulation and vapour barrier that makes repair much more complicated. 
If you can get at the wire from the opposite side in a closet or similar discreet space, that can make things much easier.
Unless you painted very recently and have leftover paint, even color matching you probably won't get it 100%, and if you just paint over a spot on the wall, this is usually noticeable. Instead, if you paint the whole wall, the fact that adjacent walls (around corners) don't match 100% is not noticeable. Keep this in mind when choosing where to cut (eg, choose smallest walls possible). 
It may also be possible to get at the wire somewhere directly:


If outlets cross doorways, there's a good chance the wire runs under the floor, and if it's an unfinished ceiling underneath, you can tap into the wire there. 
You might also be able to get at the wire in the wall, but this may be a bit of a guessing game. Non-contact circuit detectors (many stud finders have these) can help. Cut a small hole to inspect before cutting a bigger one to work in. 
You'll probably need two junctions to have enough slack. Keep in mind all j-boxes must be permanently accessible, so you may need to add an outlet or blank faceplate to make this work. 





Small variation is you could disconnect the outlets from the switch, and keep the circuit you drew for the switches/lights in place exactly as-is. This could be good depending on how you want circuits loaded out (eg, the lights/fan separate from the outlets) and what you have available -- it's very hard to say for certain without being there.