The route I took:
Since I was traveling east to west on the Southern Tier, I took highway 385 from Marathon, south through the park, camping first at a dry, primitive site (Nine Point Draw) just a few miles south of the park's north entrance, then two nights at the park's Chisos Basin Campground (not to be missed, great views and hiking), an out and back trip down the Ross Maxwell Scenic Road to Cottonwood Campground at Castolon (very remote, but beautiful ride and quiet campsite near Rio Grande River; you can also access via Old Maverick Rd, a dirt 4wd road, if you're up for an adventure, depending on the condition of the road - check with a park office or ranger). After leaving the park's west entrance I camped in Study Butte-Terlingua, then proceeded along the stunning but challenging River Road/FM170 through Big Bend Ranch State Park to Presidio (has hotels and services, but no camping). From here, I proceeded north on highway 67 (no services on this long stretch) to Marfa, which is a fantastic small town with a lively arts/music culture, numerous art galleries (including the Donald Judd/Chinati Foundation art complex), numerous great cafes, bars and options for both camping and hotels. It's a shame Marfa is not on the ST route. It was one of my favorite towns of the entire coast to coast trip. After spending two days in Marfa, I continued on 17 north to Fort Davis, where I rejoined the Southern Tier route.
Some notes on the roads:
For the most part, these are generally lighter trafficked roads with decent shoulders. There are times of the year that they'll have more recreational or tourist traffic (spring break and around Thanksgiving, in particular). My experience is that drivers were friendly and used to seeing cyclists - often stopping to make sure you're doing okay, may offer you water, etc. With the exception of a few winding sections (River Road and the road to Chisos Basin, in particular) there were pretty good sight lines and visibility. There are, however, some long, challenging stretches with little or no services which can making self-contained touring a challenge (Alpine to Marathon; Marathon to Stillwell Store, which is off-route 6 miles; BBNP north entrance to Panther Junction; Lajitas to Presidio; Presidio to Marfa).
I do not have experience on Highway 118 from Alpine to Study Butte - Terlingua, though I've heard it's a pretty ride. I don't believe there are any services along this road, which is approximately 80 miles in length. It has been ridden by many (see links to Russ Roca and Laura Crawford's writings below) and the route you mentioned above should work out fine as a way to see the park with a short detour from the route (though I wouldn't miss Marfa!).
If you plan your days right and get an early start on the long riding days, you can make it to overnight camping locations - there are great campgrounds in the NP and generally some nice private campgrounds in most of the towns (Marathon, Study Butte/Terlingua, Lajitas, Marfa) in the area. You may be tempted to stealth camp along the roads, but I would strongly discourage it. Land owners and ranchers in the area are very protective of their properties (and have been supportive of cyclist tourism in the area, so we wouldn't want to lose their support), and most of the lands along the roads outside of the national and state parks are barb-wire fences with cattle.
Special gear / food notes:
You'll want to make sure to carry plenty of water (I carried 3 bottles + a 100 oz bladder at times), snacks, patch kit and spare tubes (goat head thorns are very common in the region). There are bike shops in Alpine (Bikeman) and Terlingua (Desert Sports). The French Grocer in Marathon has some basic parts and patch kits. There are groceries available in Marathon, Stillwell Store / RV Park, at each of the three campgrounds in BBNP, at Study Butte - Terlingua, Lajitas, Presidio and Marfa - though choices can be limited in many of these locations, so you may have to get creative at times with your menus and meal planning.
Here are some additional resources for information on touring in West Texas and the Big Bend area.
Map of BBNP and surrounding towns:
Russ Roca and Laura Crawford's article in AC magazine on touring in West TX:
An additional post on their blog (with google map and links to camping/businesses):
List of local services and accommodations (with a focus on Study Butte/Terlingua area) via Desert Sports' website. These guys are also a great resource for cycling in the area.
A great local resource for West Texas/BB area info is Beth Nobles, executive director at Texas Mountain Trail, who is involved in cycling tourism projects in the area. Her email is firstname.lastname@example.org. She is very knowledgeable of the area and is a cyclist herself.
Their website, complete with cycling resources is: http://www.texasmountaintrail.com/index.aspx?page=1359
Also be sure to check out their daily blog with lots of great history on the area, restaurant reviews, and other helpful information: http://www.texasmountaintrail.blogspot.com/
I hope this helps with your tour planning!