Where does the term "heads or tails" come from?
Solution 1:
I don't think tails has anything directly to do with what is on the other side of the coin, but rather it is an expression of opposites: the head is at one end of spinal column, the tail at the other (think 'dog' nose to tail are opposites, rather than head and feet). The expression can't make head nor tail of it expresses this concept of opposites, and may be where heads or tails comes from.
The first recorded use of "tails" to mean the reverse side of a coin occurred in a 1684 comedy, "The Atheist," by playwright Thomas Otway. A character in the play advises someone, "As Boys do with their Farthings ... go to Heads or Tails for 'em."
As far as the coin toss goes, it is far from recent. Cross and pile was played in England for many centuries. The cross was the major design element on one side of many coins, and the pile was the bottom part of the die used to cast the 'cross' side of the coin. Brewer's Dictionary of Phrase and Fable (1898) Samuel Butler used the phrase in the 1600s: “Whacum had neither cross nor pile.” (Butler: Hudibras, part ii. 3.)
Before that, it was done by the Romans, and was called navia aut caput ("ship or head"), as some coins had a ship on one side and the head of the emperor on the other.
Solution 2:
Some of the earliest known coins were found in the ruins of of Lydia in modern-day Turkey. These coins date back to 600 BC, and were engraved with the image of a symbolic animal.
The "obverse" of these coins was usually the head of the animal (or the full animal), such as the famous Lion-head coin. This could explain where the etymology of "heads" and "tails" (as the "back" of the coin could be considered the "tail" of the animal.)
The more obvious answer would be that the terminology started with the Romans and Greeks, since they used heads of states to adorn their coins with (as well as Gods, such as the head of Athena coin). But I wouldn't know where the "tail" terminology comes from in that case.
It's worth noting that our knowledge of the Lydians being among the first cultures to produce coins comes mainly from the Greek historian, Herodotus. So it's likely that the Greens and Romans were inspired by the designs of the Lydians.
More information on the terminology used in other languages for the obverse and reverse of a coin. And according to Merriam-Webster, the origin of the term "tails" for the reverse of a coin in English dates to 1680.
Solution 3:
The term is heads or tails in America or Britain but it differs in other countries based on their monetary history. I know that Italy has Heads or Crosses and back in the Roman days there was Heads or Ships. Heads is a given. Most coins have a picture of a leader or powerful figure on one side and the opposite side whatever.
In the US we did have a Buffalo nickel that had a tail on the back but I am sure that the phrase was muttered before that nickel. It is just that tail is the opposite of head. The phrase "I can't make head nor tail of it" has nothing to do with coins (I think).
So the phrase is more about the actual money than just making up a phrase to play a game. And in your picture is a big dragon's tail.
Solution 4:
Growing up in Canada, this seemed a very natural expression, as most of our coins have animals on them. A beaver, caribou, loon, and polar bear adorn our five cent, twenty-five cent, one dollar, and two dollar coins, respectively.
Many other countrys, such as Madagascar and Australia also have animals on the back of their coins.