Ditto on all the above, except permits to camp on NF and BLM land are not needed. I travel extensively in a 4x4 w/camper and almost always camp on BLM or NF land for free. However, I don't get services like smelly toilets and noise from generators, radios, and drunk tourists, which are all available if you pay for a campground. When you don't use a campground, it is referred to as "dispersed camping". Just find a place you can pull off a forest service or BLM road without trampling vegetation or fragile soil, and settle in for the night. I camp just outside the entrance to the north rim, on NF roads. I've seen motor homes pulled off there as well, and you can access 90% of these roads with a Toyota Camry if you are careful.
If you are eligible (62 or over), and don't already have one, it may be worthwhile to buy the Senior Access lifetime pass for $80. It gives you free access to all NPs, as well as 1/2 off at NFS campgrounds, and also serves as a Northwest Forest Pass here in the PNW. If you are not staying at the North Rim Lodge, the next best thing is to camp at one of the NFS campgrounds just outside the park boundary (for a fee) or disperse camp. However, this means you will have to reenter the park each day at $25 a pop, unless you have the pass.
BLM land generally requires a fire pan if you want to build a fire. In June, there may be fire restrictions in place. For sure it will be hot. I never venture to the places you mention from June through August because of the heat. The north rim won't be bad, but I have seen it 108F down at the river in mid-May. I have also seen it snow on the north rim in mid-May.
Yes, reservations fill up fast, but I would keep trying xanterra.com for reservations at the north rim as they allow full refund cancellations up to two days before arrival.