Choosing an accelerometer
Most accelerometers have at least 2 axes. Below 45° the cosine varies less than the sine, above 45° it's the other way around. At 0° inclination the horizontal sensor will give a 0 G reading, that's the sine. The vertical one will give you the cosine of the inclination angle. A 0.5° rotation can best be read on the horizontal sensor. The worst case resolution-wise is at 45°. Sin(45°)=0.707, sin(45.5°)=0.713. That's a difference of 0.006. 8 bits resolution give you an LSB of 0.004, so that should be enough. Most digital sensors have a much higher resolution.  (thanks, Rocketmagnet).

That's for accelerometers with digital output. Devices with analog output have an in principle infinite resolution, however. (Note that I count PWM output accelerometers also as analog.) While digital has the advantage of a unambiguous reading (15 is 15 and nothing else), analog isn't that clear. The actual precision you can obtain depends on numerous factors, like noise and non-linearity. Noise can be taken care of by averaging over a couple hundred samples (if you have the time for that),  non-linearity by calibrating at several angles.  

edit
Rocketmagnet has a point, and you can exploit it further. You don't need a second sensor for when your angle becomes larger than 45°. Like I said, most acceleration sensors are at least 2-axis, and a single device will typically have an alignment error of 0.01°. You can't position two separate parts that accurately on a PCB. Since you have two sensors in one package, use them both and average them.


  "Oh I am just using the accelerometer for inclination sensing."


Just thinking of alternatives. How about an absolute rotary encoder? Append a weight on it and mount it so that it can rotate with as little friction as possible. A 10 bit encoder gives you a 0.35° resolution.