To make it look right, the flow of the "fire" is going to need to be animated in the opposite direction that the character on screen is moving. The cheap looking way to do this would be to take one of those animations and turn it on its side, then composite it over the video track using something like "screen" or "overlay" composite modes, or using a chroma key effect to key out the background. Even better yet, if the animation has an alpha channel enabled, you can have automatic transparency that way.

If you want to make a realistic, pro-grade effect to do what you are talking about, I would suggest looking into After Efects. The learning curve is high, but the quality is unparalleled. For this particular effect (no pun intended), you will likely end up using a plugin for AE called trapcode particular. That, or if you want to retain the cartoony look, hand animate it (using a electronic pen tablet) frame by frame, and export the frames as transparent PNG images. There's software out there you can use to 2D hand animate with, but I'm not as familiar with it.