On the origin of the expression “world’s oldest profession”, both etymonline and the wiktionary date its first recorded use to 1888. This would coincide with the use of the expression “the most ancient profession” by Rudyard Kipling in On the City Wall (1888):
Lalun is a member of the most ancient profession in the world. Lilith was her very-great-grandmamma, and that was before the days of Eve as every one knows. In the West, people say rude things about Lalun's profession, and write lectures about it, and distribute the lectures to young persons in order that Morality may be preserved. In the East where the profession is hereditary, descending from mother to daughter, nobody writes lectures or takes any notice; and that is a distinct proof of the inability of the East to manage its own affairs.
So, this is a relatively recent addition to the language (profession itself dates from circa 1200). I didn't find the exact first recorded use, but a Google ngram search clearly agrees that around 1890 is when the expression started to get widely used:
Before that, the expression had already been used and applied to other jobs, usually in pride. Some recorded uses that I could find include:
Other European languages have similar expressions, such as the French “le plus vieux métier du monde” (which translates exactly to the English).
On the issue of prostitution being or not a profession, I will quote the definition given by the New Oxford American Dictionary:
a paid occupation, esp. one that involves prolonged training and a formal qualification
So, prostitution is definitely encompassed into the broad scope of this definition. Moreover, in some countries, prostitution has a legal status that definitely classifies it as a regulated profession.