You could use software such as wowza to do converting on the fly (http://www.wowza.com/)
Alternatively you could convert your uploaded video (straight after upload) by shelling out to ffmpeg.
exec("ffmpeg -i $input -b 128k $output", $output);
and then link to the different video files depending on selected bitrate.