Applying for postdoc fellowship vs applying for lectureship
It is never too early to apply for permanent positions in academia. I would simultaneously apply for both the fellowships and lecturer positions. Once you get a 5 years fellowships (and I assume you are talking about the 5 years advanced postdoc fellowships), you can negotiate a permanent lecturer position. From the university's side, they get a person who has already been successful in obtaining a prestigious fellowship without any significant financial burden for the first 5 years (because the fellowship would pay most of your salary)! From the candidate's side, he\she gets a permanent position without having to do significant teaching or administrators duties in the first 5 years. I have seen many of my colleagues successfully going this route. These may or may not apply to Oxford-Cambridge for whom such a fellowship is not enough to offer a permanent position. But I also know people who got their fellowships hosted by Oxford-Cambridge, and then negotiated a permanent position with another university in the mid-way during their fellowship, i.e., porting their fellowships to another institution which offered them permanent positions.
In fact, I view this as a great way to transition from a postdoc to permanent position. 

I wish such an option was possible in the USA. In the USA, such 4-5 years 'fellowships'(CAREER awards) can be applied only after you secure a tenure-track position at a university.