From your name I assume you have the SS car. If thats the case, then you should run the X-Patterns that came with it. I've been running both nitro and electric touring cars for a few years now and never found a tire that gripped better on all sorts of surfaces (parking lots and such) and wore better than those X-Patterns. You can't go wrong with those.

As far as getting tires off wheels, yeah, you can if you really have to. I've heard of people boiling them, but acetone seems to work reasonably well to get 'em off (nail polish remover). Your best bet is still a new set of wheels, but with some care and patience you can get them off and still have a good wheel left over.