Madison, about 15-20 miles east of the West Yellowstone entrance (can't remember- sorry!), will not turn you away, at least as of last year when I passed through the park in early June. This was according to the park personnel administering the campground. It is along the Trans Am route, if that is the route that you will be taking. Grant Village is also along the route, but it was not open when I passed through, so I cannot answer for that. Also, Colter Bay in the Tetons has a cyclist/hiker-only area, so you will have a spot there if you need it. Between the two is the Flagg Ranch on the Rockefeller Parkway. Probably no guarantee of a spot, but my guess is that the crew there would do what they could to fit you in.