Just to get some hunches on the table, I suggest we start off with a little bit of deduction here.
First of all, we know that even as late as the Mesolithic period in Europe, Asia and Africa, human populations were relatively extremely low, with very spare population/territory ratios. Anthropological studies of human groups (in places like the (sub)Arctic, Tierra del Fuego, the Great Basin and other areas strongly suggest that under these conditions, territoriality is not a social trait, and this is particularly true in hunter/gathering societies. Aggression directed inward is dangerous for such groups, and outward aggression rarely gets a chance to develop because of the infrequency of contact; moreover, in the absence of fixed resources, such groups, even under conditions of relative abundance, tend to find their food supplies by roaming, exhausting the resources available in one area before moving on. Defending a fixed territory would be pointless even if there were someone nearby to defend it against, that sort of thing. So such groups are almost certainly low-violence groups, and it seems very unlikely that there would be the systematized comprehensive combat systems covered by the term `martial art' = (comprehensive) combat skill set.
We find territoriality coming in under two conditions:
(i) in contexts favorable to agriculture, the Neolithic Revolution leads to both fixed territories occupied by groups who can count on, and must therefore defend, fertile land which can yield dependable harvests year after year; these same dependable harvests increase the likelihood of survival for more individuals. More people, fixed land translate to both territoriality and pressure on the carrying capacity of the fixed territory. Since this is happening across the board in a give larger area, we wind up with a bunch of increasingly large groups struggling to accomodate their growing populations and increasingly turning to aggression against other such groups in order to occupy additional desirable areas.
(ii) in certain unusual contexts where agriculture is not known but game is abundant and predictable, e.g., the North Pacific coast and the the high plains of preagricultural western North America, reliable heavy runs of fish or regular migratory movements of buffalo or similar resources yield a similar effect: territoriality and serious armed intergroup conflict. These do not appear to lead to full-scale protracted conflicts that we would want to label war, but they do put a premium on skills with weapons.
As population densities increase, social stratification becomes more evident; there are many arguments amongst anthropologists as to why (or at least there used to be, way back when some of my best friends were anthopologists :wink1

. The point is that somewhere in the course of things, increased population, competition for resources within as well as between groups and improved technology for weapons production to support this intergroup conflict leads to higher levels of violence requiring systematic training in the use of weapons and the maintenance of both standing armed forces and law enforcement personnel.
The first great cities we know about—those in the Valley of Mexico and the Andean high plateau, in the Indus Valley, on the Yangtze, on the Nile and the Tigris-Euphrates Valley—all seem to be the culmination of cycles of conquest that begin along the lines I've been sketching; it's likely that they represent several thousand years of increasingly dense societies forcibly constructed by waves of intergroup fighting. One reasonable place to start one's quest for the oldest martial art would be somewhere between the full-blown Neolithic Revolution on the one hand and the appearance of the first great cities and fully stratified societies supporting professional armies as a necessary condition for their own survival in the face of attacks by other such cities.
That means that, on this scenario, you are looking at a time frame somewhere between, say, 11,000 years ago at the lower end and maybe 8,000 years back for the most ancient cities in the Middle East. This is all of course a bit rough. But it probably gives the right order of magnitude.
I also strongly suspect that the first martial arts were weapons-based, and that empty-handed fighting systems arose as extensions of weapons-based systems. We know that this has happened in at least one instance: as Iain Abernethy points out,
many of the Minimoto samurai took Okinawan wives and remained upon the island for the rest of their days. The bujitsu of the Minimoto samurai had a large influence on the fighting methods employed by the Okinawan nobles. One part of Minimoto bujitsu that had an influence on the development of karate was the idea that all motion is essentially the same. Whether striking, grappling or wielding a weapon, the Minamoto samurai taught that all combative methods relied upon similar physical movements... the results of this combat philosophy can still be seen in modern day karate.
(
Bunkai-jutsu: the Practical Application of Karate Kata, p.6.) My
guess would be that military systems of weapons applications preceded civilian empty hand systems, that the latter arise only under rather more specialized circumstances than the former (enforced occupation by a colonial power in the era preceding firearms) and that something along the lines that Abernethy sketches for the relationship between weapon and empty-handed jutsu systems may well be involved in the evolution of unarmed martial arts.
So these are my hunches. And before they can be defended even seriously, they need to be subject to the most stringent investigation against the available evidence, to the extent that we can find any. If we can't, then they remain unsupported speculations without the faintest claim on anyone's belief; all one can say on their behalf is that they comport well with various ethnological and archaeological data and show goodness of fit with known historical events. But they remain nothing but hunches. Still, you have to have a hunch to start with if you want to get any further, eh?