Ideally you would want to keyframe the cartoon heads so that they follow the video smoothly. With something like After Effects that would be a pretty straight forward task.
In this case, since you're looking for free options, you can convert an avi to a series of still images with
AVCutty, then use pretty much any paint program and do the heads by hand.
You might also want to look into
Blender, which granted it has way more features than you need, but it's got a pretty fully featured compositing portion.
Other tools worth looking at that may or may not help you:
Jahshaka
Wax
Videocharge
zs4