You're right, AT&T has horrible coverage. No, you cannot at this point use it on Verizon, a CDMA technology network (iPhone is GSM). It was almost enough to make me give up on iPhone, but in the end I couldn't do it.
Depending upon your area, other GSM networks might be a solution for you if you are willing to jailbreak and unlock your iPhone. T-Mobile in the US was good when I used it; there are others in Canada and elsewhere.