Lots of questions embedded there.
In external mics, if you'll be outdoors, try some small omni mics from Church Audio or Sound Professionals. Those should run ~$100 and another $50 or so for the battery box.
For a multi-channel mix you will need a multi-channel recorder, or two recorders that you combine later. I believe the cheapest multi-channel recorder is the Zoom H4N, which is of somewhat dubious quality but can do what you're describing.
For an SBD you need three main types of connections (plus whatever you connect to the recorder with) - RCA, XLR and 1/4". The good news is you can buy one set of XLR cables and one set of RCA cables, and then get adapters for the rest. My deck takes XLR and 1/4" inputs, so I have a set of 50' long RCAs, with 1/4" adapters to plug into the deck, and several sets of XLR cables, again with 1/4" adapters. That covers me. The Zoom H4N takes XLR inputs as well, but as I have not used the deck, I'm somewhat hesitant to recommend it. It is, I believe, the cheapest and simplest option for what you are doing, though, and has the advantage of recording all four channels at once, so you don't have as many issues with syncing (though if you're running SBD, assuming the venues are of any size, you will have to align the recordings again).
Zoom is $300 new, so that plus some Church Audio mics and a battbox puts you at $450. You can probably buy a used one for less.
http://www.amazon.com/Zoom-Handy-Portable-Digital-Recorder/dp/B001QWBM62From looking at the spec sheet, I believe when the Zoom goes 4-channel it requires that two of the channels be its included onboard mics. If you look, the writeup specifically describes doing what you are doing (SBD+onboard mics). I have heard the onboard mics on it are alright, so for $300 this could be a simple and effective route.