I know this is an old question but none of the current answers are the recommended way anymore. This is the guidance from the ffmpeg wiki. Note that all of these options do require re-encoding the video.
Speeding up/slowing down video
You can change the speed of a video stream using the setpts video filter. Note that in the following examples, the audio stream is not changed, so it should ideally be disabled with -an.
To double the speed of the video, you can use:
ffmpeg -i input.mkv -filter:v "setpts=0.5*PTS" output.mkv
The filter works by changing the presentation timestamp (PTS) of each video frame. For example, if there are two succesive frames shown at timestamps 1 and 2, and you want to speed up the video, those timestamps need to become 0.5 and 1, respectively. Thus, we have to multiply them by 0.5.
Note that this method will drop frames to achieve the desired speed. You can avoid dropped frames by specifying a higher output frame rate than the input. For example, to go from an input of 4 FPS to one that is sped up to 4x that (16 FPS):
ffmpeg -i input.mkv -r 16 -filter:v "setpts=0.25*PTS" output.mkv
To slow down your video, you have to use a multiplier greater than 1:
ffmpeg -i input.mkv -filter:v "setpts=2.0*PTS" output.mkv
You can smooth out slow/fast video with the minterpolate video filter. This is also known as "motion interpolation" or "optical flow".
ffmpeg -i input.mkv -filter "minterpolate='mi_mode=mci:mc_mode=aobmc:vsbmc=1:fps=120'" output.mkv
Other options include slowmoVideo and Butterflow.
Speeding up/slowing down audio
You can speed up or slow down audio with the atempo audio filter. To double the speed of audio:
ffmpeg -i input.mkv -filter:a "atempo=2.0" -vn output.mkv
The atempo filter is limited to using values between 0.5 and 2.0 (so it can slow it down to no less than half the original speed, and speed up to no more than double the input). If you need to, you can get around this limitation by stringing multiple atempo filters together. The following with quadruple the audio speed:
ffmpeg -i input.mkv -filter:a "atempo=2.0,atempo=2.0" -vn output.mkv
Using a complex filtergraph, you can speed up video and audio at the same time:
ffmpeg -i input.mkv -filter_complex "[0:v]setpts=0.5*PTS[v];[0:a]atempo=2.0[a]" -map "[v]" -map "[a]" output.mkv