Ok, if you're going to remove it all, I would try heat first.

If that doesn't work, try a solvent - start easy with something like paint thinner, or mineral spirits, and move up to acetone if needed (Do all of this outdoors! )

For re-covering, try Sig Coverall, or any of the "TEX" fabrics (Solartex, worldtex, etc)