(Lots of) Home runs are good
You are correct that you want to run a cable to each room from the central switch. In fact, I would run at least 1 more cable than you think you will need to each room, and consider running a line or 2 to other rooms as well - especially if your walls are open. Cable is cheap, and pulling 4 cables instead of 3 is no more work when done at the same time. If you decide later that you want a 4th jack, you either need a small switch (which does limit bandwidth, not really increase latency) or you need to open walls again to pull that 4th cable.
Use a patch panel
Rather than run the cable from the big switch to each room, you should have a patch panel in between. Patch panels basically change the type of connection on the cable (the back is a 110 punch down block, front is an RJ-45 jack), and are a simple pass-through.
This is to ease installation. Pulling cable through walls is best done when the cable is un-terminated. Terminating the cable (i.e., putting the RJ-45 jacks on the end) can and is done, but punching the cable down into a patch panel is so much easier, especially for someone who has never done it before (and it sounds like neither you nor your electrician has). The cost is marginal (again, go bigger than you think you need now), but you save on headaches during installation.
You would then get keystone jacks that allow you to punch down the cable on the other end:
You shove these into wallplates on an electrical box or low-voltage plate:
They make wall-plates with different numbers of openings (usually 1-6), so you can get what you need for each room.
Finally, you would need short (1-2 ft) "patch" cables to connect the patch panel to the big switch. Buy these cables pre-made, as you won't be able to make your own for less. These are typically stranded cable, as it's more flexible.
Your final setup would look something like this:
(the top-most device with jacks is the patch panel, the middle on is the switch, and the bottom would be your router)
Buy solid copper UTP (unshielded twisted pair) cat5e or cat6 cable, rated properly (usually CMR for typical in-wall installation, but you'll need Plenum if you plan to run it in HVAC ducts), and buy multiple boxes if possible. Standard is 1000 ft but smaller lengths are available, and they come in all different colors. A decent-sized house could take 2000-3000 ft of cabling or more, depending on how many runs and where the network closet is. Again, the more boxes you have, the easier installation will be (you typically pull 1 from each box at the same time, so if you want 4 runs to a single location, having 4 boxes is easiest).
If you want things a little cleaner, you can get a wall-mounted mini rack as well:
Just make sure to get one that has the depth and vertical space (measured in "U") you need. They also make ones with hinges that make patch panel installation a bit easier.
Most product images taken from monoprice.com
You can buy flat Ethernet cables. I'm betting you could get one under the door and still allow it to be closed.
Another option is a powerline Ethernet adapter. This is a set of modules that plug into your power outlets and allow you to transmit network signals over them. You run a patch cable from the router to a module in the same room, then plug in a second module in the room the second PC is in.
Also, if the rooms are next to each other, look around ducts, pipes that might pass through, etc. You might get lucky and find a gap big enough to fish a cable through.
Another option is to install low voltage boxes in the drywall with RJ45 jacks. Wire the jacks together, color to color, and use patch cables from the router to jack one, and from jack two to the second PC. Just leave them when you move and it will look like any other jack in the wall.
And lastly, have you considered WiFi?
Best Answer
If this were my house, I'd figure out where those cables are on the other side of that wall, and pull them back into the house, patch the holes, and arrange connections inside.
The only outside gear should be that provided by the service providers, and they will bring wires inside the house to your connections.
The electrical codes really don't say much about low voltage wiring, which this all is. You can run wires in walls, provide connection plates, etc. Do it safely and sensibly.
To figure out what goes where, look into signal tracers as mentioned in other comments.