According to Wikipedia, the velocity factor of coaxial cable is given by:
$$ VF = \frac{1}{\sqrt{\varepsilon_r\varepsilon_0}} $$
where $\varepsilon_r$ is the relative permittivity, a material property of the insulator, and $\varepsilon_0$ is the permittivity of vacuum, a constant.
So the velocity factor is determined by a single material property of the insulator and not dimensions. (An earlier edit of this post incorrectly stated that dimensions were involved, sorry.) I would think that for coaxial cable with a solid (non-foamed) insulator, the velocity factor is fairly consistent, because the uniformity of polyethylene from commercial suppliers is quite good. The velocity factor of coaxial cable with foamed polyethylene insulator may not be as consistent, because its velocity factor depends upon how much air gets into the foam. Foamed polyethylene, as used in popular coaxial cables such as LMR-400, makes the cable have lower loss than solid-dialectric cable.
I haven't been able to find specification documents defining RG-213, RG-8, or RG-58, but all the examples for sale on the internet that I saw have solid polyethylene dialectric, so the military specifications probably require solid PE to be the insulator. So I would think that the velocity factor of milspec coaxial cable is fairly consistent.
It's hard to say how accurate the quoted velocity factor of a given coaxial cable is. You might get some anecdotal evidence from hams, but the accuracy of their measurement techniques is unknown. If you're counting on a piece of coaxial cable to be a certain electrical length as part of an antenna system design, and you require a certain degree of accuracy, then you're probably better off cutting the piece long, measuring its electrical length with the help of an antenna analyzer or VNA, and then trimming it to be exact. Once you've done that, calculating its true velocity factor would be easy, and then you'd know how accurate the specification is for your piece of cable.