You don't need a VPS if you are on a tight budget. You can look for ffmpeg hosting or if you have advanced knowledge of UNIX you can use something similar to dreamhost;
FFmpeg - DreamHost
Agreed VPS is a lot easier if you have the knowledge and budget.