Proxies used to (and some still do) compare last-modified and date, if the date header is present. [0] They are not required to trust this header as accurate.
For reference around and clarification around the Date header, the "should" comes from the loophole that nobody is required to have a time source. The previous RFC's made that harder to understand, as the loophole was in another section.
I believe you have mis-interpreted Section 7.1.1.2 of RFC 7231, specifically it is identical to RFC 2616 Section 14.18 in that a Date header MUST be included except for 3 exceptions. They have listed the 3 exceptions first and also the wording that includes "SHOULD" which defines when the origin server should compute the date, but notwithstanding those notes it still notes that the Date header is mandatory for an origin server: "An origin server MUST send a Date header field in all other cases." (where other refers to the 3 exceptions -- HTTP 500-class errors; HTTP 100-class message-less responses; and no-clock systems)
A time source isn't required, a clock is. Further, if the origin server does not have a clock, any proxy (such as HAProxy) is still required to add the Date header if it has a clock, as if it were the origin server. In practice, there are very few functional systems without clocks.
I'd imagine its original design was so that the proxy could choose to honor the response date, rather than just use the current time - technically speaking the date header removes state from the proxy, as the proxy doesn't need to know what time it is to honor cache policies.
