Measuring duration and distances between pulses
I certainly wouldn't be trying to do this with a Arduino (remember, you asked what I would do).  Measuring characteristics of pulses at 500 kHz rate is going to be tricky.  The big question you left open is how close does it need to be, or more accurately, how close to you need to know it is to the perfect 500 ns and 1.5 &micro;s timings?  If you need to know this to within 1%, for example, then it's going to be difficult and get quite expensive.

If it's good enough to sample the signal every 250 ns and live with the resulting uncertainty in timing, then it's easier but still tricky.  In that case you could sample the signal into a shift register at 4 MHz, then analyze the result in firmware.  Generting a 4 MHz clock output with most advanced micros is easy, and many will have a SPI peripheral that can be repurposed to a serial to parallel converter.

On a processor like a PIC 24H, the instruction rate can go to 40 MHz.  That only leaves 10 instruction on average per bit to process, which sounds too little for this method to be workable.

Another approach is to gate counters on for the high and low times, and thereby get a count of the number of clock ticks between edges.  You still have 1M edges per second to deal with, or 40 instructions per edge.  That still sounds tight, but possibly doable depending on what else you need to do and what has to be done with the result.  The 24H has "input capture" modules that do most of this in hardware, but the firmware still has to make sense of the resulting duration measurements.

Note that your pulse train has a average level of 1/4, which might be possible to exploit with some cleverness and depending on what else is going on, how fast you need it, and a lot of other things you haven't said.