Well, I was training in the Elite four... and for some odd reason I saved before Steven with only those pokémon left:

Manectric lv. 54
72 HP left
Thunderbolt 0 PP
Thunder 9 PP
Bite 11 PP
Flash 20 PP

Shedinja lv. 53
1 HP (duuh!) (holding Focus band)
Shadow ball 9 PP
Cut 30 PP
Confuse ray 9 PP
Grudge 5 PP

Sceptile lv. 54
69 HP left
Leaf blade 9 PP
Dragon claw 11 PP
Giga drain 0 PP
Return 17 PP

The only items I have that would possibly be of any use are:
Blue flute x1
Yellow flute x1
Full restore x5
Full heal x8
King's rock x2
Super potion x2
Calcium x1
Elixir x1
Rare candy x22 (but I won't use it if possible)
PP up x1

So, I have two questions:

1) Do I have any chance to beat him without candying my pokémon?
2) If yes, how?

Yes, I am stupid... never save in the middle of the Elite four except you're positive you will win... I tried a few times, but I never make it...