Yellowstone is one of my favorite places to go and I have been there many times.
Rather than going all the way to Billings and over to Bozeman (unless there are other reasons to go there), I would suggest getting off I-25 at Buffalo, Wyoming and going to Cody, Wyoming. In Cody, there is the Buffalo Bill Center, a great museum, and they have a nightly rodeo that the kids may enjoy (although the younger one may be a bit too young).
When leaving Cody, there are two options for driving to Yellowstone. You can go in the east entrance or a more scenic drive would be to go via the Chief Joseph Scenic Byway, that takes you to the northeast entrance.
As for trails in the Yellowstone area, there are a couple of gravel roads in the park. I recall one being named Blacktail Plateau Road (or something similar). The other one leaves from the Mammoth Hot Springs area and goes toward the northwest entrance. They are so-so.
Not sure if you are planning on going to Teton National Park (your pass for Yellowstone will get you into Teton also), but there is a great 4x4 only road in Teton NP. It is so good that Toyota has filmed commercials on it. The road has great scenery and is not too difficult. I suggest taking it North to South in the park. It is shown on the Park Map as being 4x4 only, and is on the west side of the Snake River. The road takes one along the edge of the bluff overlooking the Snake River and on the other side you see the Tetons. The drive was fantastic.
If you happen to get further into north central Montana, I drove the Missouri Breaks Back Country Scenic Byway last summer. I drove it from West to East and got 20 miles in and found a washed out creek crossing and had to turn around. There was no complaints on turning around as I only missed 3 miles of the end of the route and the scenery on the first 20 miles was superb.