Using ninjas to buff and sustain him would help him.

There are teams with Pain Jigokido to make sure him heal and in case revive him and he can be found in the Tendo Treasure. However, you can get him for free as well so don't waste your seal scrolls just to get Jigokido as you might get him as a free draw.

Kazekage Gaara can help out with buff via auto barrier and you find him in Kage treasure with a chance of 1/8 for every 50-60 pulls.

Edo sasori and jinpachi can be used to buff him and allow him to 2x his standard. Both can be found in GNW treasure with a chance of 1/8 for every 50-60 pulls.

One of the reasons why you will see kisame-deidara teams is to allow deidara to use the mystery on turn 2 and build his crit rate every time a clone dies (kisame's mystery creates clones). I'm sure you know from seeing other forum posts that sailor sakura is a good choice to have and is a cheap event ninja.

Without Samehada, friendly f2p.

Water, Han, Jinpachi, Edo Deidara

Water, Kage Gaara, Edo Deidara, Sailor ^

Earth, Sailor, Jigokudo, Edo Deidara,

Earth, Jigokudo, Edo Deidara, Masked Man***

Earth, Jinpachi, Jigokudo, Edo Deidara,

Earth, Jinpachi, Edo Sasori, Edo Deidara

Wind, Kurenai, Roshi, Edo Deidara ^

Wind, Kurenai, Onoki, Edo Deidara ^

Fire, Han, Edo Deidara, Kurenai

---

^ This team can bombard everything round 2. High aoe and fast clear, very effective in GNW and Bond.

Kage Gaara can be farmed if you're level 95+ from last Elite Instance. Once a day, he will be 5 stars in no time and keep farming, since he has breakthrough.