Yes, if the output is up to 12VDC, you will need to use a voltage divider to bring that down to a safe voltage. For standard resistor values, I'd consider something like a 10k and 6.8k resistor combination (which makes for 4.85vdc). But if you have a big set of resistors, you can do even better than that.
Place the two resistors in series, where one end of the 10K resistor goes to the pulse output of the GPS unit and the other end is attached to one of the digital pins on the arduino. Then attach one end of the 6.8K resistor to the same digital pin and the other end to GND. You have to share GND between the GPS sensor and the Arduino as well.
While ISRs have great value, I'd consider perfecting the code first before using an ISR. That minimizes your potential points of failure and code optimization (if an ISR will do that) can happen later. Let me give you an example.
I have a power measurement board that samples two analog channels pretty much as fast as the ADC allows. This routine runs about 2x faster than the analog.read function allows because I'm addressing the ports and the ADC directly. None of the power measurement code uses a ISR because they gobble up 51 processing cycles every time they are invoked. At my sampling rate, the code would consume 510k cycles per second just to drop into an ISR... and the impact is measurable.
However, I do use an ISR to signal to the code that the time is up and that the previous set of power measurements has to be summarized and sent off to the main CPU (basically, the main CPU pulls a pin high on the measurement CPU and the ISR on the measurement CPU notices the rising edge). But that is one ISR being invoked every second, i.e. only 51 cycles per second lost or 1/10,000th of the above. So yes, ISRs are very useful but understand their costs and benefits before jumping in both feet. The more times a ISR has to be invoked, the greater the potential impact. That is why I only use the ISR as a signaling device.
If the main objective of your code is focused on measuring the pulses, it may make a lot more sense to not use an ISR, especially if the pulse trains are very fast (i.e. thousands per second). If, on the other hand, the pulse trains are slow (fewer than 1000 per second?) then using an ISR can be a great way to keep count of pulses while allowing the Arduino to focus on other things as well.