For thread embroidery the earliest example for Europe goes back to the Norse, 8th century. The oldest human examples are from China 3rd century BC.
As for "coats"..., well the artwork shows the outer-most garments of wealthy people being embroidered as far back as the 14th century. Whether or not you would call what the man was wearing a coat..., but by the time you get a garment that the average Joe would call a coat, thread embroidery was long established.
Not quite a "coat" but was worn over armor to help identify the individuals
Henry IV of England
So not really on the coat, but on his collar. Collar might be on garment underneath, though
Now HERE is a "coat"...not a cloak since he has sleeves and the design isn't printed, BUT alas, might be woven, so one has to decide if this needle-and-thread embroidery, or loom-thread-embroidery
Richard of York 1445
Kinge George I in the beginning of the 18th century..., I think this is his cloak, not a coat
Now the stuff isn't universal around the world. For example there seem to be times when thread embroidery isn't popular, but embellishment with rare furs is popular. Also the person's economic status and religion would also play a large part. A rich fellow might have some, but if he was of a Puritan mind set, me might not go for embroidery of any sort.
The mountian man sketch book had at least one embroidered coat, using dyed moose hair. North west traders had experimented with embroidery but could make it commercially viable.
Loyalist Dave shows it back in time. However something done in 1500 doesn’t mean it’s ok for 1800. However we do have examples of it done in America In seventeenth eighteenth and nineteenth century too
Original Eastern style fancy work was often in geometric designs. But indians started imitating European floral designs in the east very early. The Great Lakes area would find floral very appealing.
Even later in time when Buffalo hunters and frontier scouts and even cowboys sported a ‘Indian coat or vest’, it often had floral more then native geometric designs