How to configure the SPI pins(MOSI,MISO,sclk and SS) for ATMEL ATSAM3X8E

"An introduction to asynchronous circuit design" by Davis and Nowick (in particular, Figure 1 and Figure 2 and the nearby text) describes two handshaking protocols as "pervasive". The 4-cycle protocol, aka RZ (return to zero), 4-phase protocol, and level-signaling. And the similar but more complicated to implement 2-cycle protocol, aka transition, 2-phase, or NRZ (non-return to zero) signaling -- which is very similar to the "data strobe encoding" used by SpaceWire and FireWire. Either one sounds like it has most of the features you requested -- it's SPI-like in that there are exactly 4 signals, all 4 signals are one-way (no passive pull-ups), the master can pause the slave indefinitely until it is ready for the next bit from the slave, etc. It also has a feature supercat requested that SPI doesn't have: the slave can pause the master indefinitely until it is ready for the next bit from the master.

I don't know of any chips that have the 4-cycle protocol built in, but it looks like it would be easy to bit-bang on a microcontroller or a CPLD. In fact, it looks like it would be easier to bit-bang than SPI, since (like SPI) the master has no timing requirements, and (unlike SPI) the slave has no timing requirement either.

Is it possible to use the 4-phase protocol for synchronous bit transfers, and somehow build a higher-level protocol on top of that to get the other things supercat wants -- byte alignment, start-of-command frame alignment, attention/busy/idle states, etc?

I think your solution will probably work, within some constraints. The obvious one is "all SPI slaves must exhibit precisely the same bus behaviour as an Atmel 25M01". Also, I far prefer technique 1. Some specific answers:

1. A PGE on a /CS line should always cause any incomplete bus transaction to terminate immediately, so even if there is the odd spurious clock generated on selected devices that are not the current target they will be cleared in normal operation. Similarly, a /CS window that doesn't enclose any transitions on SCLK shouldn't start any bus transactions.
2. This is more of an issue. You need to be certain that this won't happen and, as noted, you will need to be clear for maintenance purposes that any new SPI devices don't actively drive the MISO line until they receive a "read" command. You might want to consider fan-out, too; I know high-impedance outputs don't represent much of a load, but 19 of them is worth paying attention to.
3. If you don't use technique 2, then this doesn't matter...
4. SPI memory devices, particularly larger ones, are increasingly meeting JEDEC standards for communications behaviour. If you choose devices that are JEDEC-compliant then you should have no interoperability issues, at least until the standards change.
5. True, but many SPI ADC's actually use the SPI clock to run the ADC's successive approximation state machine. No clock cycles, no output. That said, they might drive the bus immediately. Back to my original point: set a standard, and require that slave devices that don't meet the standard are not attached to the bus matrix.