OK, here is your keyword. You want Picture in Picture. Since that requires 4/8 tracks, you need an advanced editor. There might be free tools (if you use Linux, there is an editor for it that may do it), but expect to spend $300 or more (if you own Studio, you can get the Avid Liquid 7 upgrade for Studio for $299.) Vegas 6 and Premier Pro are around $500+ (Liquid is $500 without the upgrade - do the math on this one, Studio is <$100 at B&M IF the upgrade is still available...) All advanced editors have heavy system requirements (see my Rigs). Other names, Canopus Edius, Avid Xpress Pro, Final Cut Pro (Mac OS X only)... Try
Videoguys for the best online prices.
With Liquid, I would import the 4 videos (Divx5, WM9, MPEG-2 with AC3 (stereo - not sure about 5.1), DV-AVI, MP@HL, almost whatever). I would drop each clip on a track (my editor is set to split audio and video on a seperate track). I would go into my effects rack and drag and drop the preconfigured PIP (left upper, left lower, right upper, and right lower) on each of the clips. Now, what to do with the sound? You have 4 different tracks playing. Mute all or some. Import new audio or create a track with SmartSound (I usually export a video segment and gen music in Sonic Fire Pro from SmartSound). Liquid only has a single-pass VBR MPEG encoder. If is a very good one, but I usually export a DV-AVI and encode it with Tsunami as AC3 stereo. That said, Liquid can do 5.1 export, but I have never tried 5.1 import - not sure on the support yet. Then use MediaChance DVD-Lab to create a DVD. It you were really fancy, you could create a submenu with all 4 originals in fullscreen.