At what point in history were Time Zones empirically shown to exist?

Time zones can't be "empirically shown to exist," because they're arbitrary divisions of the earth into chunks for timekeeping convenience. They don't exist independent of humans making them up and dividing up the Earth by treaty.

What you're trying to ask is at what point time was known to be different at different places on earth, and the answer that u/scarlet_sage linked elsewhere goes into this -- to quote from that:

Hipparchus of Nicaea (c. ~190-120 BCE) seems to have been the first person to propose using a grid system to find the position of cities (and other places) on a globe, which implies an understanding of longitude. He built on earlier work by Eratosthenes of Cyrene (c. 276-194 BCE), who had mapped the known Earth, including finding its circumference. Hipparchus' method of finding the longitude of places was to use the differences in timing of lunar eclipses at different points on the globe to calculate the difference between local time of those points; the drawback is that there was no accurate-enough method of timekeeping to lead to useful calculations. Edit to clarify: The difference in local time between observed beginning and end of the eclipses would serve, essentially, as a way to understand the longitude between places.

The knowledge that local time would be different at different points on the globe is what led eventually to what's called "the discovery of the longitude" in around 1760 or so, when two methods of reliably finding longitude using time were discovered and implemented.

Regarding

I can't imagine how anyone could have proven that time zones exist without the use of a clock, but it intuitively seems as though once clocks are invented, it would be very easy to show that time zones exist, simply by noting that a clock's measurements differ by how far east or west you have travelled.

As u/restricteddata points out in this thread, the idea that time is different in different places comes from an understanding that "noon" is a moving target -- when it's noon where you are, it's not necessarily noon somewhere else. Whether you believe in the sun rotating around the earth or the earth rotating relative to the sun, understanding that the two bodies move independent of one another and that the Earth is a sphere lets you reason out the rest pretty quickly.

You don't need to invent a clock to figure that out, and in fact

noting that a clock's measurements differ by how far east or west you have travelled

is pretty damn hard!

Although the principle of finding one's longitude by reference to how far "ahead" or "behind" you were of noon at a fixed location (e.g. Greenwich, but that's also arbitrary) was understood in antiquity, it took until 1761 for John Harrison to invent a chronometer that would be accurate enough for navigators to use to find longitude. (In fact, it took until the 1830s for chronometers to become standard aboard RN ships not going far abroad, and a complicated set of observations of either the large moons of Jupiter or the Moon's position relative to other heavenly bodies was preferred in the RN.)