Meduseld was built by Brego, son of Eorl and the second King of Rohan. The Golden Hall was completed in the year 2569 of the Third Age.
3D reconstruction of Meduseld, based on the movie depiction, which in turn is very faithful to the book description of the Golden Hall. (Source gallery)
There are many references in Tolkien's writings about this, and we can collect information about the history of Rohan, Edoras and Meduseld itself.
The Lord of the Rings: The Two Towers
In the chapter The King of the Golden Hall, Theoden reveals some details while speaking to Gandalf:
‘Dark have been my dreams of late,’ he said, ‘but I feel as one new-awakened. I would now that you had come before, Gandalf. For I fear that already you have come too late, only to see the last days of my house. Not long now shall stand the high hall which Brego son of Eorl built. Fire shall devour the high seat. What is to be done?’
But none have ever ventured in to search its secrets, since Baldor, son of Brego, passed the Door and was never seen among men again. A rash vow he spoke, as he drained the horn at that feast which Brego made to hallow new-built Meduseld, and he came never to the high seat of which he was the heir.
The Lord of the Rings: The Return of the King
Another statement about Brego being the builder is given in the chapter Many meetings, when Eomer is crowned King of Rohan:
Then a minstrel and loremaster stood up and named all the names of the Lords of the Mark in their order: Eorl the Young; and Brego builder of the Hall; and Aldor brother of Baldor the hapless; and Fréa, and Fréawine, and Goldwine, and Déor, and Gram;
The Lord of the Rings - Appendix A
Appendix A, named The Tale of Years, has an entire section describing the most important parts of the history of Rohan. It tells the history of Eorl, but doesn't describe the subsequent rulers until the reign of the ninth King Helm Hammerhand.
THE HOUSE OF EORL
[...] Thus Eorl became the first King of the Mark, and he chose for his dwelling a green hill before the feet of the White Mountains that were the south-wall of his land. There the Rohirrim lived afterwards as free men under their own kings and laws, but in perpetual alliance with Gondor.
This section reports a chronology of all the Kings too:
THE KINGS OF THE MARK
1. Eorl the Young. He was so named because he succeeded his father in youth and remained yellow-haired and ruddy to the end of his days. These were shortened by a renewed attack of the Easterlings. Eorl fell in battle in the Wold, and the first mound was raised. Felaróf was laid there also.
2. Brego. He drove the enemy out of the Wold, and Rohan was not attacked again for many years. In 2569 he completed the great hall of Meduseld. At the feast his son Baldor vowed that he would tread ‘the Paths of the Dead’ and did not return. Brego died of grief the next year.
[The year ranges given here are birth and death dates, not of reign inception/end]
The Lord of the Rings - Appendix B
Appendix B, named The Tale of Years, reports a complete chronology of all major events of the Second and the Third Ages; it is not focused on Rohan, but significant dates are given here as well:
The Third Age
2510 - Celebrían departs over Sea. Orcs and Easterlings overrun Calenardhon. Eorl the Young wins the victory of the Field of Celebrant. The Rohirrim settle in Calenardhon.
2545 - Eorl falls in battle in the Wold.
2569 - Brego son of Eorl completes the Golden Hall.
Unfinished Tales of Númenor and Middle-earth
A chapter called The Battles of the Fords of Isen gives more details:
[...]In the beginning of the year 3019 the threat from Saruman was the most urgent, and the Second Marshal, the King’s son Théodred, had command over the West-mark with his base at Helm’s Deep; the Third Marshal, the King’s nephew Éomer, had as his ward the East-mark with his base at his home, Aldburg in the Folde*
* Here Eorl had his house; it passed after Brego son of Eorl removed to Edoras into the hands of Eofor, third son of Brego, from whom Éomund, father of Éomer, claimed descent. The Folde was part of the King’s Lands, but Aldburg remained the most convenient base for the Muster of the East-mark. [Author’s note.]
Summarizing what we have gathered, we know that:
Eorl became King of Rohan on 2510, when Cirion, Steward of Gondor, granted him and his people the lands of Calenardhon.
He settled on a hill at the feet of the White Mountains; this place was called Aldburg, and it was on the Eastfold, so to the east of the place where Edoras was located.
He died in 2545, leaving the Kingdom to his son Brego, and was buried on the first of the mounds outside Edoras.
Brego moved to Edoras, we are not given a precise date, but probably since the inception of his reign; since we know that Eorl was buried outside Edoras, it is reasonable to think that Brego had already moved the court here, leaving Aldburg to his third son.
In 2569, Meduseld was completed; Brego was reigning since 24 years.
Meduseld was a large but not extremely huge building, it was similar to a Saxon/Scandinavian Mead Hall, a large wooden "meeting hall/residential palace", not a vast fortress or a castle built with stone.
(The word meduseld means exactly mead hall in Old English; an interesting article describing the nature and the appearance of Meduseld can be found here)
It is clearly stated that Meduseld was built and completed by Brego, the second King of Rohan, in 2569. There is no information about when it was started and by whom, but we can try to draw some reasonable conclusions from what we already know.
Eorl held his court in Aldburg, and lived there until the end of his days. I've not delved into the history of Edoras (yet), but even if this city was already existent in Eorl's times, it is likely that if he wanted to start the construction of a Great Hall, it would have been in his own capital.
Brego was the first King to reign from Edoras, so he had more reasons to build a Palace here; then, we must consider that when Meduseld was completed, Brego was in his 24th year of reign, as he was King since his father's death in 2545. Given the nature of this building, it seems highly unlikely that the construction could have lasted more than 24 years, even if delayed by external factors. In conclusion, we can safely assume that it was too started by Brego himself.