Sounds like the BackgroundIR class I wrote as part of my project is just what you need. It runs entirely at interrupt level from timer interrupts and pulls the length of the next pulse off a circular buffer you can fill at any time (if you don't wait too long, anyway :-).
You can find the latest version in the tarball pointed at here:
http://home.comcast.net/~tomhorsley/hardware/arduino/software.html
A lot of the code was adapted from:
(but I moved it all to interrupts).