Bed liners will eventually fail also, although hopefully slower than paint. The question is not which is better or more protective, but which is easier to remove/repair when the failure does occur.
In the bedliner vs paint failure debate, I prefer paint because you can SEE the failure sooner, so you can treat the rust sooner. Some bedliners can hide the rust until the metal is GONE!