Installing a ceiling light and rewiring switch and outlet
1. Remove the existing switch box
This may require you to cut the nails/bracket attaching it to the stud.  You should be able to accomplish this using a hacksaw, oscillating multi-tool, or any other thin bladed saw.
2. Get a flexible drill bit
They can be a bit expensive, but you're going to need one if you don't want to remove the drywall. I recommend getting the whole kit, which includes the alignment tool. It will also come with a tool for pulling cable, which might come in handy later.

3. Cut the hole in the ceiling
Use a drywall circle cutter, hole saw, jab saw, utility knife, etc., to cut the hole for the ceiling box.
4. Drill up from the switch box
If you're lucky, there'll be no fire breaks in your way. If there are, you'll have to drill through them as well.  Use the alignment tool to get the flexible drill bit to the middle of the top plate, making sure the bit is straight and plumb (you want to go straight up through the top plate(s)). Keep in mind that it might be a double top plate, so it might take a bit longer than you'd think.
NOTE: The drill bit has a little screw on the tip, so it will basically pull itself through the wood. You're not going to have to apply much pressure, just let the bit do the work. If the bit gets bound up, you'll have to reverse the drill to get it to back out.
5. Bore through the joists
Position the flexible drill bit up through the hole in the ceiling, so that it hits the joist a couple inches up from the ceiling. If you're only drilling through a single joist, being perfectly straight isn't that important. However, if you have to drill through more than one joists, you'll want to make sure that the bit is positioned as straight and level as possible.
If you have to go through more joists than the single bit can reach, you'll have to buy extensions to lengthen the bit. Another option is to cut additional access holes along the route, so you can drill from multiple locations.
6. Fishing the cable
This is the most difficult task, and might require cutting strategically placed access holes through the drywall.  Basically, use any means necessary to fish the cable between the switch and the outlet. The flexible drill bit can double as a fishing rod, and can be used with the cable pulling tool to pull the cable.
You might want to consider buying a fish tape and/or fish rods, as they'll make the job more manageable.

NOTES:
If you want to control a light and fan separately, you'll want to pull three wire cable (hot, hot, neutral, ground), instead of two wire cable.
The current switch box is too full, so you'll have to install a double gang box to accommodate the new wires and switches.
To make the receptacle always hot, simply connect the line going to the receptacle to the feeder coming into the box (hot to hot, neutral to neutral, and ground to ground).
Make sure you use the proper gauge wire.  If this is a 15 ampere circuit, use 14 AWG copper conductors. If it's a 20 ampere circuit, use 12 AWG conductors.  Check the breaker protecting the circuit, to determine the circuit ampere rating.
Make sure you turn the power off at the breaker, and verify that it's off, before beginning any work.
Make sure you install a ceiling box rated for ceiling fans, preferably one of the braced boxes.
Do your best to be sure there's no other utilities in the way, before drilling through joist.  You don't want to hit a pipe, other electrical line, etc.
If you have carpeting on the floor above, you might consider pulling back the carpet and opening up the floor.