A gold based currency can still be devalued. Simply change the amount of gold it is backed by. For example:
"Congress passed the Gold Reserve Act on 30 January 1934;...The act also authorized the president to devalue the gold dollar so that it would have no more than 60 percent of its existing weight. Under this authority the president, on 31 January 1934, fixed the value of the gold dollar at 59.06 cents."
http://en.wikipedia.org/wiki/Gold_standard
debasement even happened when actual phisical coins made from precious metals were being used:
"Throughout history, governments have been known to create more coinage than their supply of precious metals would allow. By replacing some fraction of a coin's precious metal content with a base metal (often copper or nickel), the intrinsic value of each individual coin was reduced (thereby "debasing" their money), allowing the coining authority to produce more coins than would otherwise be possible. Debasement sometimes occurs in order to make the coin harder and therefore less likely to be worn down as quickly. Debasement of money almost always leads to price inflation unless price controls are also instituted by the governing authority, in which case a black market will often arise."
http://en.wikipedia.org/wiki/Coin#Coin_debasement