Find the moment of inertia of the tire, either experimentally by spinning it with a motor or with a torsional pendulum, or by measuring it with CAD models (warning: your properties need to be dead on for this - watch out for belting skewing your numbers).
Once you know what it takes to get the tire to accelerate, try putting it on a ramp and timing the results. Gravity should accelerate the object, but rolling resistance would dissipate energy. At low speeds wind resistance should be negligible. There should then be a difference between finishing times of the ideal calculation (which you could solve with energy) and the real trial, where the difference would be due to the rolling resistance.
Regarding your comment on static friction, I would just point out that static friction is what generates the torque that rotates the tire, it should not contribute any losses to the rotation (remember that the normal force is $g\cos{\theta}$). Remember that work (energy) is force times displacement, and so, if the tire does not slip, the static friction force doesn't act on any distance, so no energy is dissipated.
Rolling resistance causes energy loss because of the energy it takes to deform the tire and/or road. The bulge in the bottom of a tire is always at the bottom because, as the wheel turns, the tire is constantly flexing into and then out of that shape. Natural damping in the tire means that it takes more energy to bend it into shape than you get out by relaxing the tire. This is where the energy is lost for rolling resistance.
You can read more about rolling resistance at the Wikipedia entry, where it states SAE J1269 and SAE J2452 are SAE-defined test procedures to measure rolling resistances of tires.