Suppose a chip was taped out without proper timing analysis. After you get the chip back, what kind of testing is done to check if there are any setup or hold violations in the chip?
You would do the same kind of testing that would be necessary to determine whether some manufacturing defect was present.
Run the device at all of the "corners". That is, at all combinations of high and low temperature, high and low supply voltage, high and low frequency, etc. If you are worried about timing violations where chip input signals are latched then you need to also test at the limits of the specified timing for those signals. If the device fails at any combination of conditions then it may have a setup/hold problem or it might have some other defect.
If many devices fail at the same point in the test sequence you can figure out what specific function is being performed internally and narrow down the location of the design error.
One can experiment with data timing and collect statistics, of course: TI's app note on metastability gives a tester design for this, and a relationship to MTBF. Of course, it's better to predict than to test (partly because batch-to-batch variation can fool you if you do a single round of tests).