If the tires are textured using bump or displacement mapping would be viable and quick to do.

I would actually model the tread and either replace the tires with the mod or create a morph for the tires before trying the hide and replace route.

Hide and replace seems easier than modeling but would probably take more fiddling and tweaking to get right than altering the mesh itself would unless you get lucky with the replacement tire selected.