Solvent for tire rubber
As it was mentioned in the comments, finished rubber is a cross-linked polymer, and this is the main reason why getting vulcanized rubber liquefied without destroying it seems to be a nearly impossible task.
Also, there might be other additives, e.g. tires are most likely going to contain powdered charcoal, so that even though one can dissolve the rubber by destroying the cross-linking $\ce{(-S-S-)_n}$ bonds, charcoal is likely going to form another phase, and who knows what might happen to other additives during this process.
Finally, at the end you have to somehow recreate cross-linking for the rubber to retain it's elasticity, and this doesn't happen on its own by just evaporating the solvent (see vulcanisation).

In general, the majority or rubber types can be affected by:


strong oxidizing agents (to the extreme of being irreversibly destroyed);  
aromatic and chlorinated hydrocarbons (both have a tendency to soften rubber).
Visually it appears as if rubber is swelling; this can happen if one keeps rubber in chloroform or xylene for an extended period of time – for instance, this property is sometimes used to fit rubber tubing in place.


What I suggest is to use a so-called rubber mix or rubber compound: a semi-finished mix of [natural] rubbers, vulcanizing agents, plasticizers, fillers and additives (carbon, chalk, kaolinite etc.).
Rubber mix is used ubiquitously in the industry to produce all sorts of rubber products, including composite materials such as rubberized fabric.
Rubber mix is a versatile material which is highly viscous at the room temperature, but softens upon heating to approx. 100 °C and can be dissolved in volatile organic solvents (even benzene and gasoline).
The drawback is that at the end you still have to use vulcanization to crosslink the rubber.