There was no doubt that visiting the set of Jonah Hex was going to be an adventure from the get go, as the press kit warned us that we were going into undeveloped country. Wear boots, jeans, long-sleeved shirts, hats. Pack bug spray and sunscreen. Do not wear flip flops or heels. We've had snakes, bugs, and alligators on set! (Advice that would be repeated when we arrived on set: "Anywhere you step, kick the grass first. There's a lot of snakes here!") But when you're off to meet the cowboy with over 800 kills to his name, you're stepping into his snake-bitten world, and mosquitoes are the least of your problems.

The frontier was a trip back in time in more ways than one, as it allowed me to experience the scars of Hurricane Katrina firsthand. I hadn't been to New Orleans since I was a teenager, and I was keen to see how the city had recovered. The result was comforting and haunting, as I was relieved to see most of my favorite landmarks remained untouched, but that neighborhoods around them were, which was disorienting. Blocks that had held houses and apartment buildings were still empty, and nearly retaken by the persistent Louisiana greenery. Houses and restaurants throughout the French Quarter were still boarded up, with streaks of brown indicating where the water level had risen. Those that had reopened smacked of fresh paint and repair. The impression was reminiscent of a Western boom town, and that's really what New Orleans is now – a city waiting to be reclaimed and made rich again. It's the perfect place for Jonah Hex to hole up in.

Our visit took us out of the French Quarter, past the Ninth Ward and sunken shells of supermarkets, houses, and restaurants, and into the swampy backwoods of Louisiana. A short hike took us from the modern base camp and into a U.S. Army camp of the 1870s, filled with rows of tents and blue uniformed soldiers. The frontier army was a mix of Civil War re-enactors and hired extras. It was pretty easy to spot who was who. The re-enactors were "on" and alert even if the cameras were currently off, sitting with their hats propped on their bayonets and "cooking" on their fires. The extras were chewing gum, drinking Cokes, and talking on their cell phones.

We're led to the tent of Lt. Grass (Will Arnett), which is a big, roomy thing befitting his rank. Will Arnett strides out of it as we watch, resplendent in a full-sleeved shirt, silk waistcoat, and Victorian mustache. He's observing a group of soldiers "wiring" telegraph poles. Forlornly watching the march of technology is a poor captive in a prison wagon. As exciting as this is, we're looking for Jonah Hex himself, the man with no face. Where is he? Is he still in his trailer? Is he even in this scene? Suddenly, he's there, full of swagger in his rotten duster and Confederate hat. I'm not being dramatic, as Josh Brolin will prove he's tapped into some kind of supernatural power throughout the course of the day. One minute, he'll be in front of the camera and the next he'll be standing beside you, or you'll see him striding away from the monitors when you hadn't even seen him there at all. It's more than a little unsettling.

The Hex fans among our group are craning to see his face. Jonah Hex isn't known for his duster, boots, or hat, he's known for the grisly scar that leaves a gaping hole in his cheek, and an eyeball budging out of its socket. But Brolin is in just enough shadow that we can only see it that it resembles raw hamburger. We have to wait a little longer to get up close though, because it's time for action. Arnett's voice booms across the field. "Gaze on the future, Mr. Hex! Once these wires are strung up, we can stop that g--damn Turnbull and his second rate attacks!" One of the soldiers wiring the poles hits a live one, and electrocutes himself, falling to the ground. Hex smirks. "Future's bright."

He's not a man concerned with a little thing like electricity, and instead strides over to the prison wagon to meet Grass' captive, a preacher who may have some vital information on John Malkovich's Quentin Turnbull. (If you think Jonah Hex is drenched in nothing but steampunk and the fantastic, know that he's got some history worked in where you least expect it. The production designers reveal the grim prison wagon was based on an original they found at a plantation, where men would be left for three or four days at a time.)

When they break, we're introduced to director Jimmy Hayward. He's likable, brash, and funny and is impish with what he won't tell us. "[Jonah Hex] is an origin story set among origin stories," Hayward says. "It's kind of like the legend of Jonah Hex, and how he got the scar on his face. [It's his] whole back story of who he is in reverse, starting with this murderous, scarred bounty hunter, and finding out how he got that way, tearing off the layers, exposing who Jonah Hex is and why."

Fans will remember that Hayward came on board with a fair bit of sniggering, as the Horton Hears a Who director replaced Mark Neveldine and Brian Taylor. I asked him about the negativity that followed his hiring, and he grins, proud of having caused an Internet outcry. "I loved it! I thought it was funny ... It's like, if you know me as a person and as an individual, you're surprised I directed Horton Hears a Who!, not this! But people out there are like 'He directed that and he worked at Pixar! That's all he's capable of!" Brolin had complete faith in Hayward, and couldn't stop praising his enthusiasm and creativity. "With Jimmy Hayward on the set, it brings a kind of I don't know, a spasmodic adolescent tone to it, and I like that, because he doesn't know what the rules are yet. So anything goes with Jimmy. He brings an incredible energy to it, and he doesn't understand what not to do, and I love being around that. It reminds me of Robert Rodriguez."

While Hayward was full of praise for Neveldine and Taylor's treatment (praise that was echoed by Brolin and Andrew Lazar), he was also determined to make something more than a bloody shoot-em-up. "We based the movie off their original script, and then I rewrote a bunch of stuff. I kept a bunch of their stuff ... There [was] a lot of 'Look at the bone snapping in half!' I'm not interested in that as a filmmaker ... I've got John Malkovich in this movie. He puts a gun to somebody's back. Do I want to watch John Malkovich's murderous face as he pulls the trigger? Or do I want to watch the blood fly out of the guy's heart? I want to watch Malkovich's eyes. That's where I'm kind of going with this movie."

But if you're thinking Jonah Hex abandoned all of the Neveldine / Taylor craziness in favor of a serious and Unforgiven route, you're dead wrong. "Every time Jimmy gets the chance to burn something down and have Hex walk out of it, he's gonna do it," says visual effects supervisor Ariel Velasco-Shaw. "We're aiming for a redefinition of the Western ... There are some very fantasy like, dark elements with respect to Hex. Hex is essentially Clint Eastwood, but in a more fantastical world, in the comic book world. He really is hard to kill. He's High Plains Drifter's guy, he's the Man with No Name, he's Pale Rider's Preacher Man, he's all of that, but even more so. That's even more what we're supposed to try and achieve."

The unearthly angle of Hex was a big part of the character's appeal to Brolin. "I love having that luxury. We can pull off anything and justify it, because of that, and no one can really call us on our sh*t. No 'Well, Jonah Hex doesn't do that.' Well you know what, Jonah Hex can do whatever he wants, whenever he wants, whether it's here or in the afterworld. It becomes, to me, very metaphysical, very spiritual, existentialist. That's what keeps me interested. I may be full of sh*t, but that's what I create in order to keep me interested."

But don't expect Jonah Hex to spend too much time messing with zombies and voodoo. "The supernatural is there, but it's subtext, it's kind of an underpinning," says Andrew Lazar. "It's definitely a subtle use of it in this one. We don't want the trappings of the supernatural to overtake what's really important which is introducing who this character is and what makes him special ...There's an underpinning to Jonah's character that's always going to be the mythology of [having] one foot in the grave, and one here on earth. That's always going to be prevalent." Fans who have seen the trailer are focusing on that, but on set, the emphasis was all on the characters and the fun of trying to recreate the boldness of spaghetti westerns. "It's a hardbitten Western that has a very simple but elegant revenge plot," says Lazar. It's a real exciting action movie that on one hand feels like a Western, but on the other hand feels a little heightened, a little bit stylized like it came from a comic book."

Shooting stops as we're talking, and no one notices Brolin until he silently appears at our table and startles everyone. He's an intense and imposing man, but much the uneasiness really stems from his make-up. All of his good looks are buried beneath layers of gruesome, raw latex. There's no bulging eyeball, but they've kept the skin flap over the mouth. His face is twisted into a permanent Eastwood sneer, with rotten teeth visible through the hole and scar tissue of his lip. None of us can stop staring, and there's something in Brolin's demeanor that suggests he's careless and self-conscious about it, just like the Hex of the comic books. When he smokes, he's forced to plug up the hole in his cheek to inhale. When he breathes through it, it's accompanied by a slurping, wheezing sound. It's pretty gross, and its perfect for the character. I certainly hope they let his natural sound effects and obvious discomfort show onscreen.

Brolin is sick and weary from a long shoot, but he's so fully in character that you're half-convinced it's because he just rode across miles of prairie and desert. Left alone by the cast and crew, he sits down, puts his boots up, puts his hat over his eyes, and falls asleep. He's not doing this for our benefit. Brolin is Jonah Hex inside and out. As he clinks around set, it's impossible to think of anyone more suited to the character. All I can do is hope that all the promising talk and cultish dedication translates into the film they described to us.

There's been a lot of rumors, reshoots, and changes to the film since we visited the set last May. We've seen a trailer that suggests the supernatural plays a much bigger part than was hinted on set. But regardless of what that film ends up being, there was enough promise that I hope it all comes together in a way that allows Hex to keep on riding. I want to see him send more souls into hell, riding the western wastelands with only the acrid smell of gunsmoke as his companion.