Every year the ballot includes all of the usual candidates up for election that year. It also includes a referendum for each office not currently up for election:

"Shall there be an election for the office of [President, Governor, U.S. Senator, etc...] next year?"

More than a simple majority should be necessary for the referendum to pass- let's say 60%. If it passes then the election is scheduled for next year and the current officeholder and any challengers have that long to campaign for it. Otherwise the incumbent continues until the full term expires: 4 years for President, 6 years for Senator, etc. at which time a regular election is scheduled. US Representatives aren't part of this system since they all have to run every two years anyway.

If an election takes place in an off-year under this system, the "default" term is unchanged: e.g. the next US Presidential election is 2008. Suppose the referendum passes in 2009, causing an election in 2010. The winner of the 2010 election serves until 2012, the next scheduled election on the 4 year cycle, and in 2013 there will be a referendum to have an election in 2014. Got it?

This provides the year-to-year accountability of the Random Elections idea but puts the time frame in the hands of the voters. As a side effect, every year would see good turnout at the polls which I think would be a benefit to local races in off-years.