I use some software called ushare to stream video from my pc to my Xbox 360. I won’t go into the details on how to set that up, it’s pretty straight forward. Chances are good that your linux distribution already has a package for ushare built.
If you find yourself with a video encoded in H.264/x264 (it’ll probably have a .mp4 file extension) you will be frustrated to find out that the Xbox 360 won’t play it. There is an incredibly easy workaround to this. Just change the .mp4 filename extension to .avi.
Not sure exactly why this works, but I have a feeling it’s simply due to the .mp4 filename extension. The Xbox 360 must assume it doesn’t know how to play mp4 files, without actually checking to see what codec the video file needs. But that’s total speculation on my part.