That seems a really good idea, although it needs a little tweaking.
Perhaps instead of sending all cards back into the deck, it could just be the used cards? That way you don't have to go through the slow set-up that some matches have. Plus, it avoids people getting decks full of fireflies/skeletons.
I can see a lot of a new deck ideas that could be made for this type of battle if it was to be made into an AI option - it could be implemented for each level, so players of all skill levels can have a go at this mode.
I agree there should be a modified reward, however I'm not sure extra slot spins would be the right reward. If you have an extra long God fight, you can possibly earn a lot more upgraded cards, but with an anti-god deck you can take one down quickly, so more spins for less cash (and even if some Gods' decks are made to last longer, strategies would appear to farm them quickly).
Also, what would happen if I have 30 card deck and my opponent has 60? Would I have to wait before my deck is reshuffled, or would both players be reshuffled as soon as the person with the lowest cards hits zero? Personally, I'd say you have to wait, that way you don't get the advantage of a reshuffle and your opponent doesn't get the disadvantage of an early reshuffle.