The first part of the phrase, "every man has his price" is apparently a mis-quote of a remark by Robert Walpole, made in 1734, that "I know the price of every man in this house (i.e. the House of Commons) except three", although it is believed that the phrase was in common use before this time.
The oldest combination with "all the gold in ... couldn't buy ..." that I could find is an anonymous political pamphlet about William Pitt the Younger, titled:
The Freedom of England in Contra-Distinction to Pitticism: addressed to the Freeholders of the County of Lincoln in particular, and to the Freeholders and Electors throughout England, Ireland, Wales, and Scotland in General.
as quoted in The Fireside Magazine from January 1819, p.62:
When Mr. Pitt's proposition for parliamentary reform, in 1783, was followed up by the meeting of the Thatched House Tavern, to take the sense of the people upon the conduct of the House of Commons, government were alarmed indeed. The test could not be stood, they knew ; therefor, as the life and soul of this dreadful measure could not safely be destroyed, he must be corrupted.
Every man has his price, said the ---- to his friends, go and buy Pitt. Buy Pitt! your -------- returned they, with every mark of incredulous surprise. Buy him, buy him, returned the ----, with his accustomed eagerness. Daddy Jenky now saw what his master was driving at, and made the best of the matter. Your -------- is aware, that all the gold in the Bank of England were insufficient to buy the son of Chatham! Gold, gold, gold! said the ----; no, no, no, nor ribbons, nor dukedoms neither, will buy Pitt!
I assume the censored words are "king" and "highness", and "Daddy Jenky" is Robert Jenkinson, 2nd Earl of Liverpool.