As far as the "liner" on the floor, actually I think it's a sound absorbing material, on one side of my truck it was peeling up in spots. I was able to pull up a corner and grab hold and pull the whole thing up in one sheet. Didn't even need a heat gun, just came up like a big piece of tape. The drivers side was stuck down pretty good, must have been the heat from the exhaust. I scuffed the surface real good, trimmed off any rough edges and bedlined over the rest of it. Over a year now with daily use and no issues.
And to answer your other question, I myself, did not go all the way to paint before applying bedliner. I brushed on a good coat of rustoleum primer on the bare metal and repaired spots (welded the cracks in the floor from the original seats) and used the afforementioned POR Patch on any welded seams. Instead of heeding Ryokens warning, I applied the Herculiner right over the primer and POR stuff instead of painting first. I am prepared to live with my mistake but didn't want to lead you down the wrong path. So, my advice to you is not to do what I did and go all the way to paint before applying bedliner. You do what you want, it's your truck.