These shoes are as classic as they come.
I am not sure if it means that its style won't be affected whether the trend changes as time goes. Does it mean that this item is a timeless piece?
"noun is as adjective as they come" is an expression meaning that "noun is extremely adjective".
It's a way to indicate emphasis that stands out more than just saying 'very'. Depending on the situation, it can be as strong as "There is nothing more adjective than noun."
He is as smart as they come = He is extremely smart.
Your car is as junky as they come = Your car is extremely junky.
So your example could be read as:
Those shoes are very classic.
There are no shoes more classic than those.
or even as
I've never seen shoes as classic as those.
As to the use of the word 'classic' in referring to apparel, see definition 1c (MW)
characterized by simple tailored lines in fashion year after year