Before you spend enormous amounts of time trying to score a old card you may wish to consider what you need the power for. The free drivers are not very performant in games and may not support all the card's features. That's just the way life is -- ATI and NV spend enormous resources into optimizing drivers for likely game applications and fixing breakage where it occurs. You don't need a 1950 level card to do basic desktop effects.
As a Linux user you have to choose between having a 100% open system and functionality when it comes to 3d hardware. I managed to soothe my guilty mind by considering binary drivers as no different than firmware -- the whole thing is a black box to enable functionality.
Also, there is another open source driver effort other than radeonhd. That one does support the R700 GPUs, including the 4870/4850 but not including the 4760. None of the open source drivers enable video playback acceleration. I could be a bit out of date, I gave up trying to get ATI hardware to work properly on linux over a year ago. Head to phoronix and find out!