1) Recording services (weddings are just another service). We don't know what the lighting is at your church. Most I've been to don't have very good lighting. If you don't want grainy video and can't improve the lighting, then large lenses and imaging chips are required for the camcorder.
2) CDs hold only 700mb of data. If you are going to compress the video a lot, then that will work - but playback on a regular DVD player will result in extremely poor video quality. Playback of computer-readable video files in a small window (way smaller than those you see as the YouTube default video window) might work. Full screen will look terrible. Do you mean DVD?
3) Video capture software? Camcorders record video and audio. Transfer the video (with audio) to a computer for editing. Video editing software is required - for editing. After editing, burning to a DVD means a DVD authoring application is needed. We don't know what computers you have available to do this. Windows XP (SP2 and newer) is bundled with MovieMaker - a decent DVD authoring app needs to be investigated and acquired. Apple Macintosh OSX is bundled with iMovie and iDVD.
Any applications included with the camcorder in the box are useless and unneeded.
4) Overhead projector connections and switching between different video sources depends on the overhead projector. You ask, "Is it possible to switch between the video and what the PC is projecting?" Since we don't know what projector you are using, we have no way to know. Generally, yes, it is possible to do by selecting the video source using the buttons on the projector - but this assumes all the video sources are connected to the projector. Do you also want to connect the camcorder to the projector?
Before we jump to suggesting camcorder manufacturers and models, it would help to be clear on the requirements.
"Low and mid-budget options" is not too helpful. Low and mid compared to what? It sounds like you want pro grade, broadcast, quality. It also sounds like you want the cameras (I did not use "camcorders" on purpose) to feed a control room recording station where the video is stored for later editing and possible broadcast. The cameras used are not camcorders in this environment - and you will also need a separate system for audio.
If "low-mid-budget" means $10,000, then this *might* be do-able but *very* challenging. If it means $200 or $2,000, in my opinion, I don't think you can get there from here and produce a quality end-product suitable "for later broadcast on the public TV".
The wedding videographers I know have spent $3,000+ on a single high definition camcorder. Add in over $1,500 for a couple of different mics - including wireless clip on and hand-held gear, $400+ on a decent fluid head tripod, field audio recorder (even though camcorders record video, audio is captured separately), cases, power packs and a bunch of other stuff. At least two I know have a couple thousand dollars invested in a camera crane, dolly and SteadyCam/GlideCam vest system... most use more than one camcorder... and we have not even gotten to the computer hardware for editing or the DVD duplicator systems plus the better video editing applications (Final Cut, Adobe Premiere, AVID, among others) that have lots more flexibility... and the time it takes to learn to use all this stuff...
If the control room concept is what you are looking for, then the cameras, video mixer and audio system - and all the cabling and various recorders are a very different proposition.
I'm looking for a camcorder to record our church services and occasional weddings. We would save them on CD's. Is seperate video capture software needed or does it come with the camera? We have a PC in the room for the overhead projection of powerpoint and videos for the service. Is it possible to switch between the video and what the PC is projecting? If we decide to edit the service for later broadcast on the public TV, what additional software is needed?
What are the low and mid-budget options available?
poerpoint

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic