You cant fit 35's with less than about ÂŁ5000, the fact you mentioned budget rules this out as an option for you.
You could bodge yourself the space to physically get them in for a few hundred with a horribly large bodylift and a spacer block suspension lift. Although im not sure on the width, you would probably have to run spacers and then cut the arch lips so they didn't catch.
Then you need to strip apart the rear axle and fit new ring an pinions, (only available from the states) and you will definitely have to pull apart the front end, fit an M205 axle from a nissan titan (again shipped over from the states) as the standard navara RD149 front diff is not upto 35's and you will just crack the casing. This will also have to be re-geared to match the rear ring and pinions. Then to run the standard Navara front end, you will have to get some custom half shafts made to match the M205 diff to the navara hubs.
Theres a reason very few Navaras/frontier's are running 35's, its an expensive game.
Rich