Install mencoder:

# yum install mencoder

Or in Ubuntu:

# aptitude install mencoder

Convert:

$ mencoder video.mkv -oac mp3lame -ovc copy -o output.avi

MEncoder SVN-r1.0~rc3+svn20090426-4.4.3 (C) 2000-2009 MPlayer Team
success: format: 0  data: 0x0 - 0x45ebeb4a
[mkv] Track ID 1: video (V_MPEG4/ISO/AVC), -vid 0
[mkv] Track ID 2: audio (A_AC3) "English AC3 384kbps", -aid 0, -alang eng
[mkv] Will play video track 1.
Matroska file format detected.
VIDEO:  [avc1]  1280x720  24bpp  25.000 fps    0.0 kbps ( 0.0 kbyte/s)
[V] filefmt:31  fourcc:0x31637661  size:1280x720  fps:25.000  ftime:=0.0400
==========================================================================
Opening audio decoder: [liba52] AC3 decoding with liba52
Using SSE optimized IMDCT transform
Using MMX optimized resampler
AUDIO: 48000 Hz, 2 ch, s16le, 384.0 kbit/25.00% (ratio: 48000->192000)
Selected audio codec: [a52] afm: liba52 (AC3-liba52)
==========================================================================
videocodec: framecopy (1280x720 24bpp fourcc=31637661)
MP3 audio selected.
Writing header...
ODML: Aspect information not (yet?) available or unspecified, not writing vprp header.
Writing header...
ODML: Aspect information not (yet?) available or unspecified, not writing vprp header.
Pos:   1.0s     24f ( 0%)  0.00fps Trem:   0min   0mb  A-V:0.081 [0:202]
Skipping frame!
ODML: Starting new RIFF chunk at 1023MB.:   0min 1070mb  A-V:0.059 [3148:227]
Writing index...98f (99%) 526.01fps Trem:   0min 1073mb  A-V:0.043 [3163:228]
Writing header...
ODML: Aspect information not (yet?) available or unspecified, not writing vprp header.

Video stream: 3163.546 kbit/s  (395443 B/s)  size: 1045504459 bytes  2643.880 secs  66098 frames

Audio stream:  228.468 kbit/s  (28558 B/s)  size: 75509568 bytes  2644.032 secs

Where:
video.mkv - the video source
-oac mp3lame - convert the audio to mp3
-ovc copy - copy the video quality. No re-encoding.
-o output.avi - the output video.