I did this in a Linux Mint 11 64-bit machine (Ubuntu 11.04-based).
At long last, my struggle is over.
Huge thanks to Campbell Barton and to Davis Sorenson for the patience and tips while I was in IRC at the #blendercoders channel (such a friendly place, btw!)
However, I wouldn't have made it through without the user who goes by the alias Cobe571. Without him linking his guide, I would be stuck and would have to probably wait for better seamless support in Blender and ffmpeg. It can really really be a pain to set all these up. The last minute, I almost gave up and just decide to use the premade builds available at Graphicall (which are really handy if you want something out of the box).
Thoroughly, I followed Cobe571's guide over at http://wiki.blender.org/index.php/User_talk:Cobe571. However, I had to do few modifications on my own since my system didn't recognize or was not able to execute some of the commands mentioned. Namely, under the section "- Compiling FFMPEG in a non default path", I had to remove "--enable-libgsm" and "--enable-libdc1394". Don't ask me what they are for, I personally don't know. Then finally, when I executed Blender (from the /install/linux folder), it couldn't find certain library dependencies, in this case "libavfilter". So I went ahead and did a "sudo apt-get install libavfilter-dev", and that did the magic! Now I'm able to run a Blender with ffmpeg support compiled on my system.
Many many thanks to you guys!
Again, I highly suggest you go over this page > http://wiki.blender.org/index.php/User_talk:Cobe571