I read somewhere that FaceTime over 3G (or the blocking of) is controlled by the carrier. So, like when AT&T finally supported MMS on their network they pushed out a carrier update through iTunes, I would think that as carriers start allowing FaceTime over 3G, they'll push a very tiny update through iTunes. Of course, this is just based on whatever the heck article it was that I read that suggested that. If that is true, then Apple would have already had to include the appropriate compression and whatnot to do decent video calling over 3G.
EDIT: I think perhaps I misread the original post. I thought you were asking what would have to be done to use FaceTime over 3G, but it looks like you meant with phones other than iPhone.