I have taken my KJ to Big Bend twice, one when it was stock and once after the lift and tires. I have wheeled the whole park.
Yes, there is gas in the park. There is a little general store with food, showers, fuel and other things. It is located towards the river side.
When it was stock, I hit my front skid plate on everything imaginable but other than being annoying, there was not problems. Considering that there is about as much ground clearance as a Civic, then it is to be expected. Yes, you can get though Black Gap with a stock KJ.
After the lift kit and tires, nothing in the park is even a challenge.
There are no 'difficult' roads there, just a lot of back roads where you might need a 4wd in a few spots and high clearance that the KJ dosen't have so just mind the rocks and you will have no problems at all.
Black Gap is the most challenging but dosen't compair to some of the stuff in Colorado.
Email me for a few pics if you want.
mrclortho@yahoo.com