I don't mean rebellions and resistance against conversion like with Charlemagne and the Saxons. I mean a ruler who tried to convert his realm to Christianity or Islam and was replaced by a pagan ruler.
I am curious because most examples I know of seem to succeed and the rulers earns greater legitimacy and is sometimes later proclaimed a saint.
The main problem concerning OP's question is that the violent confrontation between newly converted Christian ruler and his stubborn subject almost became topos (the common episode) in early medieval hagiographical literature (i.e. the life of holy ruler regarded as a saint by some (not all) people). It means that a hagiographer could portrait/ disguise the death of a dead ruler as a religious martyrdom who fell in the battlefield in different circumstances by victimize his opponents as 'the stubborn enemy against the Christians'.
While I suppose the attempt of newly converted ruler to promote the mass-conversion further among the his subject 'from above' sometimes was one of the chief factors of his unpopularity, the exact cause of this kind of ruler's exile was often unclear if we take various possible factors into consideration. In many cases, we don't often have enough amount of relatively 'unbiased' contemporary accounts to validate or to deny this kind of claim in the hagiography.
[Added]: To give an example, King Harald Bluetooth of Denmark (d. 987) was died in exile against the rebellion led by his own son, King Sweyn Forkbeard (d. 1013). It is true that Sweyn was hostile to the Christian clergy from Germany, however, but we don't have enough evidence that he was hostile against all the Christians in the beginning of his reign. Even the German Christian scribe (Adam of Bremen) admits that King Sweyn introduced the Christian missionary from England, not from Germany as his father had done. In other words, it is likely that the German scribe [Adam of Bremen] disguises the real conflict cause between Father King Harald and Son Sweyn as Christian between Pagan, not as German and English missionaries as it had perhaps been.
Some 11th century 'Swedish' rulers like Olof Skötkonung (d. 1022) and Ingi I (Stenkilsson, also called 'the Elder') (d. ca. 1110?) are indeed said to lost their popularity and to be expelled from central Sweden (Svealand) when they tried to restrict or abolish the traditional (and notorious) sacrificial feast allegedly held in 'the temple' of Old Uppsala, Sweden, but OP's definition does not apply even to their cases, due to the complex nature of the political structures of 'Sweden' around 1100.
I can mention one more interesting example: King Håkon the Good of Norway (d. 961). While the 13th century saga author portraits him as a failed pioneer of imposing Christianity that he was familiar with in Anglo-Saxon England, the 10th century poet commemorate his death in totally pagan manner: In the lay of Håkon (Hákonarmál), the alleged converted Håkon was admitted to Vallhalla, escorted by valkyries. We don't know whether he was really an apostate or an pagan poet made use of his death in the battlefield as a kind of 'pagan martyr', though.
References: