The Merchant is the Genie
This is the most widely accepted version of the theory. It describes how the Merchant from the first scene is actually the genie in human form. This makes sense because Robin Williams voices both characters. Another variation of this same theory says the man made it up to sell the lamp.
In one scene of Disney's Aladdin, Genie calls Al's clothes "so last century". Genie was trapped in the lamp for 10,000 years, so there is no way he could have known about the fashion trends which could have happened whilst he was in the lamp. Which means the latest Genie could have been trapped in the lamp during the 3rd century. If he spent 10,000 years in the lamp, it is then at least 10,300 AD when he gets out.
Aladdin takes place in the future, or more exact, a post-apocalyptic world where only Arabic (and some Greek) survived. Its been so long that the name "Arabia" has been corrupted into "Agrabah". The Islamic religion has atrophied to the point where there are no mosques, imams or prayer mats, but people still give praise to Allah in moments of happiness. Amazing technological marvels left behind by the previous civilization, like flying carpets or genetically engineered parrots which can comprehend human speech instead of just mimicking it, are taken for granted by locals or considered “Magic”. The Genie proves this by making impressions of ancient, long-dead celebrities like Groucho Marx, Jack Nicholson, etc."
In addition to this, in the Aladdin genesis video game there's a modern-day stop sign buried in the sand, as well as a number of bones/skeletons. (http://youtu.be/bfLyK_msMTY?t=9m17s)
Arguments Against Theory
Being that he is the genie, he is an omnipotent being with a different perception on time and reality, like a Time Lord. Genie doesn't have to be alive back then to have infinite knowledge of a certain culture. Genie is just making a quick joke like he always does. Some may argue "well why would he do that if Aladdin wouldn't get the jokes?" Sure, Aladdin wouldn't have understood the jokes the Genie was referencing, but do you really think after 8000 years Aladdin would know who Groucho Marx is? Lastly, Genie says "indoor plumbing is going to be huge", once again showing how he perceives time and referencing an event that hasn't happened.
As the video game is not directly canon, it may not be that much of a support for this theory.