Check out PagePlus, prepaid carrier that uses Verizon's network.
I live in Montana, similar situation with Verizon being the only network with much coverage here, and have been happy with the reception I get on my pageplus phone. Not quite as many plan options/cheap pay levels as some of the other prepaid carriers perhaps, but certainly cheaper that a postpaid carrier!
Also, their website makes it look like they only have a few phones to choose from, but most verizon phones will work on pageplus so you can just look for a cheap used verizon phone.