Zioneer
Banned
The thing is, if you and the rest of the Council want Zion to be a farming colony that is relatively isolated from all those non-Saints types, Utah is actually pretty close to perfect in the early 1840s...
Especially as, don't forget, you're asking men with women and children to go there via handcart... Crossing the Divide is bad enough; crossing the Rockies and the Sierras is asking for an early Donner Party or several.
The one other possibility that seems remotely in the ballpark is the Oregon Country/Territory and/or Washington Territory, which is emptier than anywhere else on the Pacific Coast under US sovereignty at this point...
However, there are plenty of Americans going there, it gets colder the farther north you go, and it's farther away than Utah and western Colorado.
If you can push the departure date farther back then the 1840s, of course, that opens up some slightly different possibilities, but if you're trying to keep a point of departure in the 1840s, Utah/Western Colorado actually fits the bill pretty well.
Nevada and what is today Arizona are possibilities, but again, you'd be ordering your followers to go farther than what is necessary for your purposes.
Want to get really wacky? Have William Walker become a Saint and go for somewhere in Central America... It's been done before, after all.
Best,
Hmm... Could there be some sort of disease or natural disaster that causes the Mormons to keep going once they get to the Salt Lake Valley? A severe earthquake, maybe? I suppose the easier way to get the Mormons away from Utah is to make the main area of settlement temporarily unusable.
As for the difficulty of getting to California by handcart; that's actually part of my idea for Mormon California; once they're there, knowing how difficult it is getting to there by the traditional route, perhaps the Mormon immigration is geared more towards converts coming from the other direction by ship, rather than the East Coast and Europe?
Oregon and British Columbia would be an interesting options; perhaps even Montana if that isn't too cold. And I would argue that the Saints were used to cold, considering they were mainly from New England, northern England, and so forth. I mean, James Strang led his (smaller than Brigham's) body of followers to Wisconsin and then Michigan, after all.
As for William Walker, I think he was too involved in Southern nationalism to be a Mormon; most of them were Yankees and even accused of abolitionism at some point. Other adventurers might work (Allan Pinkerton could've been a Mormon, for example), but I think Walker was too big on conquering Latin America for slavery.
Though that brings me to another point; for the purposes of the story I'm writing, I want early Mormonism (at least, post-Joseph Mormonism) to have significantly different racial attitudes. Earlier non-white leaders, for example. No priesthood ban. Friendlier attitude towards various groups, etc. Part of my specific story idea is having Jonathan Napela be an apostle, for example.
I think California is a no-go, despite how cool a story it would be. Not only is it unlikely due to the huge population boom and Gold Rush, but the native Californios were pretty conservative Catholics. They wouldn't take kindly to a big group of polygamous heretics moving in illegally (essentially all American migrants to California pre-Mexican-American War were illegal immigrants; the Californio government would issue them passports anyways because they were constantly afraid of a Texas-style revolt).
That's a good point, though before the Mormons got comfortable in Utah, they weren't openly advertising polygamy yet. It was only when they felt they wouldn't have to move again (1852 or thereabouts), that they felt comfortable openly declaring their polygamy. So anything the Californios heard would be treated more like rumor for at least a little while.