As pointed out its legal to ride on highways in Arizona outside of metro areas.
I'm not sure about the area in question, but most non-metro highways, have a wide shoulder, with a rumble strip between the main road and the shoulder. A cyclist riding in the middle of the shoulder should me safe from road debris, attentive motorists and the rumble strip.