I think XMedia Recode will do what you ask (free as you requested - http://www.videohelp.com/tools/XMedia_Recode ). It will certainly accept mkv and output xvid. It also comes with an xbox 360 profile but it's only h.264 (also known as AVC). If you need avi you can just pick Custom for the profile.
You can open several files at once, give them all the same encoding options (right click the list->select all), click Add Job and Encode. It'll do all of them one after the other.
Oh, and avi is a container that holds video, usually encoded with Xvid or Divx (audio is usually mp3). So xvid and avi are not different formats, the avi holds the xvid video.
If the subtitles are hard encoded in the video, any converter will keep them since they're a permanent part of it. If they're a separate stream in the mkv, you might have to do something else to make sure you keep them. Though the last time I recommended XMedia Recode for this, the asker said it did keep the subs.
----Edit----
I took some time and read more about what xbox360 can play:
H264/AVC with AAC sound in mp4
Divx/Xivd with mp3 sound in avi
(and no soft subs inside or out - argh)
So now I can also mention that if your mkv has one or more of these codecs inside, you don't actually have to re-encode them, just change the container format. E.g. if you had an mkv with AVC video and AAC audio, in XMedia Recode after you set the format to mp4, you just check "Video copy" on the video tab and "Audio copy" on the audio tab. Not re-encoding can save quality loss and time. Of course this won't help you if you need to hardcode some subtitles.
You can see what codecs are used next to the added input file in XMR or you can install MediaInfo and check the "Shell InfoTip" option in preferences - then you can click files in windows explorer and read data in the status bar or mouseover for a popup tooltip. http://www.videohelp.com/tools/MediaInfo
You're right, XMR does not have an "add subtitle" box. I actually looked for one when I first started using it but since I don't really need it, I forgot about it. I should've thought about that before I recommended it, sorry! (I'd probably use an avisynth script to add the subtitle but that's another topic :) ).
I did find some discussions (like http://forum.videohelp.com/threads/291846-how-to-add-subtitles-in-mp4-movie ) recommending Xvid4PSP. I didn't try it but it has an Xbox360 profile and a hardcode-subtitles option. I don't know if it reads subtitle streams in the mkv or if they have to be separate files. You can read about it here http://www.videohelp.com/tools/XviD4PSP and I'd use this download link: http://www.videohelp.com/download/XviD4PSP_5037_full.exe since some have trouble with other versions and their main website loaded so slow, I gave up on it. [Edit: here's a guide: http://beans.seartipy.com/2008/01/20/step-3c-hardcoding-subtitles-with-mp4-files-using-xvid4psp/ ]
Another one I see recommended around here (I've never used it) is Format Factory - http://www.videohelp.com/tools/format_factory .
If you do have to extract the subtitle stream from the mkv, there are a few tools to do that (I tried VirtualDubMod first since I already have it and it worked for srt-type but not ssa-type). You probably already have one but I'll share this for anyone else who might be reading :)
I tried 3 and the only one that worked was MKVcleaver. It requires MKVtoolnix ( http://www.videohelp.com/tools/mkvtoolnix ). After that's installed (or just extracted, installation is optional), you then extract and run MKVcleaver.exe. The first thing you do is click "Locate MKVToolNix.." and find its directory (for me it was the same since that's where I put it), you only have to do that once. You can open multiple files and pick what you want to extract on the right. It's here: http://einsof-haras.ca/apps/
So there's a little more information, I hope it turns out ok! I was meaning to try out some MKV extractors so I'm glad this came up.