neil, i would definitely not do any exercises on you're off day. as you say, you're body needs time to recover.
unfortunately i cannot give you comprehensive advise on you're pull-up substitution questions, as i've never had to do substitutions myself.
from what i've gathered though by reading the forum (and much of my own opinion), pull-ups will get progressively easier as you get stronger in your arms as well as when you start losing weight. it goes without saying that it will be easier to lift your body if it weighs 80 kg's as opposed to 100 kg's. i don't know whether you are overweight or not, but being "lighter", will definitely make pull-ups easier.
as for the strength in your arms, that will come in time - hence you have to do substitutions. just be patient!!!
lastly, in stead of pull-ups, try doing chin-ups. you might just be surprised by the fact that you cannot do a pull-up, but that you can easily manage a chin-up and voila - gone are the days of substitutions!!!