Yes, the TSOP1738 will do at this short distance. The 0.65 relative responsitivity means that at 36 kHz your IR LED needs to be \$\sqrt{0.65}\$ = 0.8 times closer to see the same signal strength, due to the inverse-square law. So if your TSOP1738 sees a certain level for 38 kHz at 1 m, you'll have to hold the transmitter at 80 cm to get the same signal strength at 36 kHz. BTW, with a remote control with fresh batteries I measured perfect reception at more than 15 m distance, so no problem at all.
Don't worry about the PIC's performance. The TSOP1738 won't output the 38 kHz signal. That's the carrier frequency, which is removed by the TSOP1738 to get back the baseband signal, which has a much lower frequency, with pulse durations in the order of 1 ms, so there's plenty of time to measure time between edges accurately.
The following scope images illustrate this:
This is one RC5 code. The top signal is the 36 kHz modulated signal, the bottom the baseband signal with the actual code.
This is zoomed in on one pulse of the baseband signal. You can see individual pulses of the 36 kHz carrier.
One more word about the carrier frequency. You may be using a remote control which you don't know this frequency of. The TSOP1738 doesn't give it on its output, so if you want to read it you'll have to connect an IR photodiode or transistor to one of the PIC's inputs and read the time between two same edges. That's feasible. Period times for different carrier frequencies:
40 kHz: 25 µs
38 kHz: 26.3 µs
36 kHz: 27.8 µs
A 20 MHz PIC16F616 has an instruction cycle of 200 ns (it divides the clock by 4!). So readings for the three frequencies should be about 125, 131 and 139. That should be enough to tell them apart. But if you want you can let a number of edges pass and only read the timer after the 10th interrupt, for instance: 1250, 1316, 1389. Not too much longer because you have to keep the time shorter than one pulse of the baseband signal.
Success!
Programming one PIC by another PIC is perfectly possible, and when you use LVP the circuit is trivial. The effort is in writing the code on the master PIC that implements the programming algorithm, according to the specs in the 'programming specification' document for the slaved chip. This is what most programmers (the hardware thingies, not the people) do, but note that in most cases the programming algorithm is at least partially implemented in the PC side software.
There are various examples that you can check, the pickit2 has already been mentioned. My Wisp648 firmware (in Jal) and PC side software (in Python) are also open source, and IIRC the software for Olin's programmers is too.
But the programming specifications are not that hard to read an implement from scratch, especially if you need to support only one target chip. Essentially you force the chip into programming mode (release reset while LVP is active), and then you feed it commands and associated data (in a SPI-like fashion), observing the required timing. Afterwards you can use an off-the-shelve programmer to check whether your programming effort was successful.
Another solution would to to put a bootloader in the F88. The down side is that you need to program the bootloader (but a suitable one might exit already) and that the bootloader takes some memory, but the up side is that you can choose the communication protocol (or stick to an existing bootloader, which will often use a UART-based protocol).
Best Answer
We're not going to spoon feed you code, because you won't learn anything that way. However, I hope we will be able to help you understand the underlying theories.
There's a number of different ways of measuring frequency. Briefly these are:
Period measuring is basically what you are suggesting in your question. Measure the time between one leading (or falling) edge and the next. For this to be accurate you need to have a timer that is capable of running faster than the highest frequency you want to measure. Your system has to be able to react quick enough to time between the edges without missing an edge.
Edge counting is a simpler system to implement and can allow for measuring of higher frequencies than the period measuring, but only gives you an average frequency over a short period. This basically works by counting the number of incoming edges of the waveform over a pre-defined period. The simplest period to use is one second. Every time an edge is seen by the input pin you increment a counter. Every second you return that count and reset it to zero. It could be done by using an interrupt pin, or a timer with the clock source set to be an input pin. The latter is more accurate at higher frequencies if you have the ability on your chip.
Gated timing is probably the most fun, but requires specific facilities on your chip. Some timers are able to run in "gated" mode, whereby they count up at the system clock frequency (or some derivative of it) only when a certain input pin is in a HIGH state. Couple that with a second timer to measure the time between gate activations and you not only have the period of the wave but also the duty cycle.
FFT, or Fast Fourier Transform, is the most mathematically intensive. However it can give you frequency information about more complex waveforms. This is probably way beyond the scope of a PIC16 but worth mentioning anyway. With FFT you record a set of samples (analog) into memory then perform the FFT transformation. The result is a set of "buckets", each one representing the amplitude of a range of frequencies. Not really what you're looking for when you just want to measure the frequency of a square wave, but may be worth knowing it exists for a future project.
So which method should you use? Well, that is very subjective. It all depends on the frequency ranges you are looking to measure, the accuracy you want to achieve, whether you are interested in the duty cycle or not, and what facilities your chip provides. Now you know more about the options you can start looking in to which method is best for you.