I’ve just updated my repository of SE Linux related packages for Lenny  to include a set of ffmpeg packages modified to not need text relocations (execmod access under SE Linux). I haven’t checked to make sure that I fixed all issues in those packages, but I have fixed all the issues that prevented Mplayer from working in a default configuration of SE Linux.
I had to patch the file libswscale/rgb2rgb.c to disable the MMX assembly code as the --disable-mmx option doesn’t work for that file. I changed the build script so that when it generates the code for the shared and cmov targets in i386 mode it adds -DPIC and -DBROKEN_RELOCATIONS to the CFLAGS and also added LIBOBJFLAGS=-fPIC to the ./configure run. There might have been a better way of doing this, but the current implementation basically works.
Long term I think that the ideal solution to this would be to have separate versions of the library packages for people who prefer extra security to a possible 15% performance benefit.
While using these libraries on an EeePC 701 (the least powerful of all the machines I own which could be used to play video) I was able to play full-screen video downloaded from ted.com without any glitches so it seems that a 15% performance loss is not a problem.