Can't comment on either end of your proposed trip, but during the "oil boom" a few years ago I did a couple of round trips between COE and SDY and Williston. Like you, I was doing it in my long-suffering, wheezing 172. Here's what I did.
An experienced Montana pilot advised me to stop at Malta, MT (M75). They had an old Suburban as a courtesy car that was well known in town. Had to pump the brakes a few times to stop the rig. Stayed at the "Maltana" motel. Older but adequate. Talked to a local pilot about routing, he advised flying south and seeing the Missouri River drainage. It was worth it. Landed at Fort Benton(79S) for fuel. On that trip we went over Rogers Pass near Lincoln, MT, and on to St. Ignatius (52S). The runway here starts to look short on takeoff at High DA in a loaded 172. From there direct back to COE.
Another time I stayed further north and fueled at Shelby (SBX) then ended up testing the old plane's sevice ceiling at 13,450'. I was trying to go through the Marias pass, but too many clouds. After picking my way through the tall rocks; stayed high at 8,500 and then direct to COE.
A few notes, (maybe a rant or two...). The "large" FBO's fueling facilities at Kalispell City and I do not get along. There is another fuel pit on the west side that worked better for me. If you have never been into S27 before, it can be hard to pick out visually as it blends in with beautiful downtown Kalispell.
Fuel is cheaper at SZT than COE. I paid $4.55 at Sandpoint 2 nights ago. If you don't have a reason to go to COE, I would avoid it. It can turn into an aerial "Wild West Show" rather quickly.
Keep an eye on the barometric readings as you travel in mountain country. Big differences between one side of the hills and the other can mean some unwanted excitement.
Have a great time on your trip!