Late afternoon in Lautoka, in Fiji's western sugar-cane belt, and the place is heaving. There must be 2000 noisy, banner-waving people camped out in the city's market square, and every one of them, it seems, wants to grasp the hand of the burly figure just arrived in their midst.

The man moving through the crush of stallholders, taxi drivers, schoolchildren and shoppers is not a rock star, but a military dictator who has ruled this Pacific nation with an iron grip for nearly eight years. For a moment, Rear Admiral (Retired) Josaia Voreqe "Frank" Bainimarama appears overwhelmed. Then he mounts a chair, megaphone in hand, and begins to speak.

On December 5, 2006, Bainimarama, commander of the Republic of Fiji Military Forces, seized power at gunpoint, overthrowing Laisenia Qarase's government and appointing himself "interim" prime minister.

It was Fiji's fourth coup in 19 years - or was it the fifth? Then, in 2009, ditching a promise to hold elections that year, he ripped up the constitution and declared martial law. Already an international pariah, the country was suspended from the Commonwealth and Pacific Islands Forum.

Fast forward to April 2014, and the mercurial leader - having announced that long-suffering Fijians will finally go to the polls on September 17 - is seeking a popular mandate. Last month, he resigned as commander; last week, he unveiled a new political party, Fiji First. Now, swapping his military fatigues for shorts and a floral shirt, he is touring the islands in a restored 1970s Bedford bus, on a mission to enlist the 5000 members required to register his party.

If his reception at Lautoka is anything to go by, the 60-year-old is a shoo-in. Although, by law, he's not yet permitted to campaign - and, as he explains to the crowd, "I don't want the other parties to send my name up to the police station!" (cue roars of laughter) - "that doesn't stop you coming to see me as your prime minister. If you have a problem, you know how to reach me." And he rattles off his mobile number, prompting a frantic scramble for pen and paper.

It's difficult to reconcile this affable showman with a regime accused of trampling human rights and brutalising its citizens. Yet this superficially enchanting country, so welcoming to visitors, is full of perplexing contradictions. And chief among them, perhaps, is Bainimarama's claim that his coup was not a coup, but a revolution, designed to create a more equal society - and a "better" democracy than the one he crushed.

The morning mist is just lifting from the jagged emerald hills flanking Rakiraki, a small town nestling in a far-flung corner of Viti Levu, Fiji's main island. In a shady spot near the bus station, Fiji First volunteers are signing up locals, including Dami Naidu, a sugar-cane farmer, who loiters in the hope of meeting the prime minister. "I just want to tell him he's doing a great job," he confides with a grin, revealing two gold teeth.

Naidu is Indo-Fijian, descended from the labourers shipped over by Britain in the 19th century to toil in the sugar plantations. That ethnic Indians - who these days dominate business and the professions - are Bainimarama's biggest fans might at first seem paradoxical, given that previous coups (in 1987 and 2000) unseated Indian-led governments, and were aimed, ostensibly, at safeguarding the rights of ethnic Fijians. This time, though, an indigenous Fijian government was ousted, and Bainimarama acted in the name of multiracialism, vowing to heal the ethnic rifts that have blighted Fiji since independence in 1970.

What about the way he grabbed power? Naidu shrugs. "He's united the whole country, Indians and Fijians, and he's helping both races, likewise." While earlier coups sparked anti-Indian violence, observes honey farmer Anil Tikaran, since 2006 "there's not that feeling all the time that something bad's going to happen ... We can live virtually without fear."

On Rakiraki's main street, I bump into Bainimarama. "Call me Frank!" he beams, before inviting me to join his battle bus, which - just like Fiji's public buses - is windowless, with vinyl seats and a deep-throated diesel engine. His wife Mary, several friends and a couple of local journalists are already on board, and, as we hit the road, his elder brother, Joe, a taxi driver, leads the way in a Toyota Crown. Like the bus, the taxi is light blue (the party colour, also the national flag's) and flaunts the Fiji First logo (a rip-off of Fiji's coat of arms).

During a two-day blitz of western Viti Levu, following a highway winding past fields of gently waving sugar cane, the dictator is mobbed by well-wishers, many of them ethnic Fijians, or iTaukei. That might seem counter-intuitive, too, because - outraging the indigenous population - he has disbanded the Great Council of Chiefs, a group of revered tribal leaders, and strong-armed the Methodist Church - to which most iTaukei belong - to stay out of politics. (The chiefs, he remarked, "should meet under a mango tree and enjoy home brew".)

Although chiefly hackles still rise at that insult, Bainimarama has redeemed himself, to a degree, by building roads and bringing water and electricity to neglected rural communities. Meanwhile, progressive policies, such as the decriminalisation of homosexuality, have gone down well with urban, educated Fijians. And, as of this year, schooling is free.

In the village of Vatukoula, the prime minister perches on a climbing frame in a children's playground to speak to locals. When Malakai Nanabalarua asks for help with a land issue, he pulls out his phone and calls the ministry in Suva. Nanabalarua is suitably impressed. "That's the kind of leadership we want," he says. A Fijian journalist tells me: "My grandmother has him on speed dial, no kidding. She calls him when the water's out."

In Ba, the birthplace of Mahendra Chaudhry, the Indo-Fijian prime minister held hostage in May 2000 for 56 days by George Speight and renegade soldiers, Shiu Kumar swears that "even if my father is standing for another party, I'll still support Bainimarama". However, another onlooker, Joseph Rogan, gives the first hint that these enthusiastic turn-outs may prove deceptive. Lowering his voice, he says: "Just because we've registered for Fiji First doesn't mean we're choosing. You can register for any party, but come the day no one knows who you vote for."

On the fringes of the crowd, an Assembly of God pastor is seething about the assault on the Council of Chiefs and the once-influential Methodist Church. The two institutions - which Bainimarama regarded as rival power bases - are the "cornerstones of Fijian culture and religion", he declares, and "if you take these away, it's like cutting off both my hands".

Day two in the west, and the prime minister is in buoyant spirits. "We're going to win this election," he tells Good Weekend. "The only question is by how much."

The poll is being spruiked as Fiji's first truly democratic election, since previous voting systems were skewed in favour of indigenous Fijians, who had become outnumbered (but now comprise about 57 per cent of a population of roughly 850,000). Fiji First's principal rival is the Social Democratic Liberal Party, or Sodelpa, founded by Laisenia Qarase, whom Bainimarama installed as prime minister in 2000 after he imposed martial law (in what was effectively a counter-coup) and resolved the hostage crisis.

Qarase won elections in 2001 and 2006, but pursued what many considered an indigenous supremacist agenda, even - to Bainimarama's fury - contemplating pardoning Speight.

Under the new constitution drafted by Bainimarama's regime - the fourth since 1970 - every citizen is a Fijian: a term previously reserved for iTaukei. "We're changing the mindsets of the people, and that's the revolution," he says, bellowing over the roar of the bus's engine.

Why did that require a military takeover, though?

"Unfortunately," he replies, "that's the only way these things can be done in Fiji."

Usually wary of the Australian media, the dictator has his guard down and is happy to chat. "Fiji can't afford for me to lose this election," he warns, "because there'll be no one to keep the revolution going. Sodelpa will come back and we'll have the same old faces and same old racist policies."

There's no risk of Qarase returning, nor Mahendra Chaudhry, still the Labour Party leader. Convicted, respectively, of corruption and fraud, following what each insists was a politically motivated prosecution, both are disqualified from standing. However, Sodelpa's candidates include Sitiveni Rabuka, the charismatic colonel who staged the nation's first coup in May 1987 (and its second four months later).

A rugby-mad former naval officer who rose through the ranks after graduating from Suva's Marist Brothers High School, Bainimarama - who spent 39 years in the military, 15 at the helm - seems genuinely colour-blind. In Nawaicoba, he tells the mainly Indian villagers, gathered in an open-air Hindu temple: "It's very important for me that my Indo-Fijian brothers endorse my party, because it's a multiracial party and I want to take all the races in Fiji forward."

Sylvester Joseph, who is on the bus tour, grew up with "Frankie" in suburban Suva. "He's a great humanitarian," he says. "And he believes in the truth - he was always like that as a young man." He also has a famously short fuse, and, some contend, is still traumatised by a mutiny in November 2000 at Queen Elizabeth Barracks, Fiji's military headquarters, during which he had to flee for his life. At the time of the 2006 coup, he was facing possible charges in relation to five rebel soldiers beaten to death after being captured.

While Bainimarama now craves legitimacy, I sense he may struggle to make the transition to elected politician. Mentioning a rival party leader who has challenged him to a debate, he snaps that "I'm the one that wants democracy here" - adding, in a reference to the 80,000 or so Indo-Fijians who emigrated following earlier coups: "He's an Indian, without me he wouldn't even be sticking around." He also recounts how a European Union commissioner offered him €500 million ($732 million) in aid if he held elections. "I said, 'You think Fiji is like some African country, and every time we have a coup you just give us money?' I nearly hit him over the head with a bottle of Fiji Water."

This evening he's invited to a village meeting in Saunaka, near Nadi, where "most of the big chiefs in the west are going to give me their support". In the event, only two chiefs turn up, but they present him with a tabua, or whale's tooth, and a choir serenades him with mellifluous Methodist hymns. Finally, in one of the more surreal moments of my time in Fiji, dozens of villagers line up to greet him, shuffling towards him on their knees.

Emerging much later, dreamily elated, he sighs: "I could have sat there and drunk kava all night, I was so happy." Then he laughs and declares: "If I was leader of an opposition party, I would give up now."

It's May 2013, and the Coca-Cola games, a schools athletics competition, are under way at Suva's ANZ Stadium. During Fiji TV's live coverage, its sports editor, Satish Narayan, grumbles about the loud music being played during races, and remarks that "CEO Litiana should do something about it". "CEO Litiana" is Litiana Loabuka, eldest daughter of Bainimarama and chief executive of the Fiji Sports Council, which runs the stadium - and Loabuka is livid. An apology, broadcast during a prime-time bulletin, fails to appease her. A month later, reportedly after her father threatens to strip Fiji TV of its licence, Narayan quits.

It's a minor incident, relatively speaking, yet it illustrates the regime's mentality: intolerant of even the slightest criticism, and unforgiving in pursuit of transgressors. Privately owned Fiji TV is a favourite target - the station was forced to fire a respected reporter, Anish Chand, only in May - and so is The Fiji Times newspaper, fined $F300,000 ($175,000) last year for publishing a claim that the country has "no [credible] judiciary". (Fiji's judges were dismissed in 2009 and replaced with pliant appointees, many from Sri Lanka.)

Not only journalists, but lawyers, academics and trade unionists have experienced official paranoia and wrath; so have civil society groups, opposition politicians and pro-democracy activists. A casual remark at a party, followed by a call to his employer, led to a lowly clerk being sacked; businesses can't afford to upset Bainimarama or his attorney-general, Aiyaz Sayed-Khaiyum. An economics professor, Wadan Narsey, says he was forced to resign from the University of the South Pacific after the authorities threatened to withhold funding. "People are terrified of being labelled anti-government," says Ricardo Morris, editor of the independent Repúblika magazine.

Perceived troublemakers are placed under surveillance, serially arrested, harassed by intelligence officers and banned from travelling overseas. Increasingly, the courts are also used to persecute opponents. In 2010, a renowned human-rights lawyer, Imrana Jalal, was charged with licencing infractions at her husband's Suva cafe, of which she was a director. A magistrate who queried the case - normally it would be dealt with by a city council - was fired; it was then, bizarrely, sent up to the High Court, which threw it out, but only after months of worry and legal bills for Jalal. She left Fiji, effectively driven out.

And then there are old-fashioned bully-boy tactics. On Christmas Eve 2006, the head of the Fiji Women's Rights Movement, Virisila Buadromo, was hauled up to Queen Elizabeth Barracks, where she was screamed at, punched, kicked, stamped on and made to lick soldiers' boots. Holding a pistol to her head, two officers told her: "We could kill you right now and put you in an oil drum out on the reef." Since then, countless other regime critics have endured similar treatment - and far worse - in military custody, with several deaths recorded. At the sugar mill in Ba, Felix Anthony, national secretary of the Fiji Trades Union Congress, was beaten up, along with his deputy, by military officers, after being sworn at by a "very agitated" Bainimarama, who threatened to "pour kerosene over us and burn us".

In Aiyaz Sayed-Khaiyum's spacious office overlooking Suva Harbour, I ask him about footage that surfaced last year of police beating and torturing two prisoners. The prime minister's right-hand man - and the author of hundreds of repressive decrees which will remain in force after the election - looks pained. "You know," he observes, "police brutality is not confined to Fiji. I've got a report at home about Aboriginal deaths in custody."

Ruthless, authoritarian, vindictive - these are some of the politer words used about the attorney-general, who performs the day-to-day business of governing while Bainimarama swans around the islands and hobnobs with new allies, including the Chinese. Editors dread a phone call from the Australian-educated Sayed-Khaiyum, who is rarely seen without bodyguards in tow. "One holds his coat, another his bottle of water, another his files," claims one local.

For all their talk of transparency and accountability, he and Bainimarama - who cited rampant corruption as one reason for his coup - refuse to divulge their salaries. It's been years since an auditor-general's report was published, and when I ask Fijians whether the government heeds its own anti-graft message, they guffaw. Rumours of dodgy tenders, foreign bank accounts and luxury properties are just rumours, obviously. And it was, surely, on merit alone that the dictator's daughter got her plum Sports Council job and his brother-in-law was given a ministry to run after being jailed for manslaughter.

The real power in Fiji rests, of course, with the military, now headed by Bainimarama's hand-picked successor, Brigadier-General Mosese Tikoitoga - and the question is: after running the country for nearly eight years, is the military really willing to relinquish control? What if Bainimarama loses the election? What if he concocts an excuse to call in the troops? Will Tikoitoga, who has praised his former boss as "guided by God", oblige?

Reclining in a gold striped armchair in his office at Strategic Headquarters, the urbane new commander tells Good Weekend that although "the prime minister is a very personal friend of mine, and we still enjoy each other's company after a few drinks ... I've made it very clear that the military has to stay out of politics now. We've gone back to barracks to await the election result ... I've also told the chief of police that it's no longer a case of pick up the phone and call the army to set up a roadblock or sort out a crowd." He pauses. "And we will not have another coup, as such - that's quite definite."

That's settled, then - or is it? Rather ominously, Tikoitoga adds that the military "will support an elected government as long as it respects the constitution ... I say that because a lot of the parties are going about saying they're going to change the constitution ... They think they can just come in and throw it away."

Like in any democracy, an elected government will be entitled to rewrite the constitution, and I wonder if he's worried about the provision that grants "absolute and unconditional immunity" to all regime figures in relation to 2006 and everything since.

Ruminating on recent Fijian history, the brigadier-general makes it clear that he believes the military rescued the nation from the brink following Speight's coup, when armed mobs rampaged through Suva, looting and burning, and terrorised Indo-Fijian farmers in rural areas. "We saw a very dark side of Fiji, and we don't want a revisit of that," he says. "That's how ethnic cleansing begins."

The 2006 coup, on the other hand, was "the revolution we had to go through ... to create a Fiji for all Fijians". There's that argument again, yet as Roshika Deo, an independent candidate, points out: "Democracy is not something you force on me at gunpoint, it's got to be made by the people of Fiji." For all the rhetoric, moreover, the military still consists almost exclusively of iTaukei - as does the public service, as does the cabinet. When I relay to Tikoitoga a story about an Indo-Fijian who, on applying to join the army, was asked, "But do you eat beef?" Tikoitoga looks sorrowful, and reveals that he's a vegetarian himself.

According to the opinion polls, Bainimarama enjoys a stratospheric popularity rating of 66 to 83 per cent. While some are sceptical of those figures, there seems little question he will poll strongly in September, particularly with the regime tightly controlling everything from party membership to funding and campaigning - while brazenly flouting its own decrees.

In spite of international input - Australia will co-lead the observer mission - many Fijians doubt the elections will be free and fair, and they accuse Australia and New Zealand of jumping the gun when they lifted travel sanctions against the dictatorship in March. Trade union leader Felix Anthony asks: "How can elections be free and fair when there's no free media, when trade unions are excluded from political life and debate, when [civil society groups] have stiff restrictions on them, when people simply don't feel free to speak out?"

Among indigenous Fijians, claims Laisenia Qarase, "the anger is building up inside and I wouldn't be surprised if there'll be an explosion ... If they manipulate the election, that could be the trigger." Others question whether the election will even take place. "Don't underestimate their capacity for bloody-mindedness," cautions one insider. "The slightest pretext, and they could flick their nose at the international community."

Notwithstanding Tikoitoga's (somewhat ambiguous) reassurances, fears of another coup still loom large. "It's 50-50," predicts Sitiveni Rabuka, who knows a thing or two about coups - and who professes, now, to regret his own hot-headedness. "At the time I felt it was the right thing to do," he explains over a pot of tea on the pool terrace of Suva's Holiday Inn. "But then others tried to follow the same path, and I thought, 'My goodness, what on earth have I started?' That's why I'm standing for election again. People keep blaming me for this coup culture, so I thought I'd better try to correct it."

The instability has played havoc with the economy - more than half of Fijians now live below the poverty line - as well as precipitating another exodus of educated and affluent Indo-Fijians. Rabuka, who made the leap to prime minister in the 1990s, calls this election "a defining moment", while Mahendra Chaudhry warns that "the nation is already on a disaster path, and if these people get in again, it will be completely ruined ... We'll have a dictatorship here in the guise of a democracy."

Troubled paradise

1987: Colonel Sitiveni Rabuka stages two coups.

May 2000: Fiji's first ethnic Indian prime minister, Mahendra Chaudhry, and cabinet taken hostage by George Speight. Military commander Frank Bainimarama declares martial law, negotiates the hostages' release after 56 days.

December 2006: Bainimarama overthrows Laisenia Qarase's government, establishes a military regime.

April 2009: After Fiji's Court of Appeal rules the coup illegal, Bainimarama abrogates constitution, institutes emergency rule.

March 2014: Bainimarama resigns from military, unveils his new political party, Fiji First.

September 17, 2014: First democratic election for eight years.