Adding offset voltage to sensor signal
My first reaction is to get a better A/D converter.  There are many many out there that can directly convert from the 0 to 5 V range.

You didn't say what the upper end of the A/D range is, but if it's 5 V, then you don't want to add a offset, but rather scale the signal towards 5 V.  Put another way, you want to map 0 to 5 V --> 500 mV to 5 V.  That's not adding a offset.

Fortunately, scaling relative to 5 V is easier than adding a offset.  All you need is two resistors: