Getting a coupler that is fast enough is not a problem, if you need zillions, you can even hit your price point. You should look at the high speed analog couplers like the PS8101. It is the closest you will get to both of your goals in the same coupler...
A single transistor coupler will work at those speeds if the circuit is tweeked for that coupler. If margin is added for temp and age, then the single transistor couplers drop to about 10-15kB.
You can switch to a high speed analog (PIN diode) type coupler like the NEC PS8101, that will get...
The relay solution is probably the easiest to implement. You can get Opto SSR's in SOP packages to minimize your board space. I would recommend looking at the 400V telecom relays, they are overkill voltage wise, but the high volumes keep the price of those relays low. NEC makes some good ones.
