Golubev and Nedovyesov never trailed after breaking Federer in the opening game and completed a 6-4, 7-6 (5), 4-6, 7-6 (6) victory.
The Kazakh pair converted their first match point when Wawrinka could not control Golubev's powerful return of Federer's serve.
"Against those guys you have to play almost the perfect match. I'm happy that we did today," Golubev said.
In Sunday's reverse singles, No. 3-ranked Wawrinka is scheduled to play the 56th-ranked Mikhail Kukushkin before Federer takes on the 64th-ranked Golubev, who beat Wawrinka in Friday's opening singles.
"I'm actually very excited for tomorrow," Federer said. "We are still the favorites for each singles match tomorrow, but with no more margin for error and we're aware of that."
The winner plays Britain or Italy in the semifinals in September. Led by Andy Murray, Britain is ahead 2-1 in Naples on the Italians' favored clay surface.
Federer and Wawrinka, the Australian Open champion, won gold in doubles at the 2008 Beijing Olympics and were loudly supported by the 16,000 spectators in the indoor Palexpo arena.
"Pretty excited, especially that we beat the Olympic champions. It makes it special," said Nedovyesov, who is ranked No. 76 in singles.
The Swiss were a service break up in the second set, but the Kazakhs broke back when Wawrinka served for the set at 5-3.
The visitors clinched a two-set lead when Federer sent a half-volley wide as he approached the net.
Federer and Wawrinka served out the third set after breaking in the fifth game.
Federer's serve came under pressure again in the fourth set, trailing 0-30 when down 6-5 before forcing the tiebreaker. Switzerland held a set point but Federer's backhand lob drifted long.
"It was two difficult days but I'm going to be ready for tomorrow," said Wawrinka, who lost to Kukushkin in a 2010 Davis Cup relegation playoff.
Federer must wait to see if he needs to play against Golubev, whom he described as "the man of the match."
"I've been very impressed by him," Federer said. "He made the difference in the doubles at the end. I'm looking forward to that challenge."