sounds like the starter contact have worn out. maybe not recommended but an easy way to test if the starter contacts are worn is: when your car doesn't start and you only get the 'click' sound from the solenoid, try giving the starter housing a couple of hard knocks while trying to start the car. if it starts up, it's most likely worn contacts.
i haven't changed the starter on my 4runner so i couldn't tell you exactly but i did replace the starter contacts in my V6 '94 4wd toy p'up and it's was very easy replacing the parts in the starter, itself, but i had a difficult time putting back the starter b/c not much working room in the engine bay but i'd say it was well worth spending a couple of hours and $20 on a starter rebuild/repair kit than buying an OEM starter for $220+. if you have the time, tools and are mechanically inclined, i'd say do it yourself. if you want more DIY info, i'm sure there's write-ups here, on other forums and if you just google it. gl.