I have decided that I hate Psychic Pokemon.
Lucian of the D/P Elite Four keeps kicking my ass. The other three I can take down with little to no trouble, but Lucian... it's his Medicham. ****ing Fighting/Psychic combo with the full range of elemental punches, meaning it has two counters to its main weakness: Flying. And the only Pokemon of mine with a Ghost move (its other weakness) is part Steel, which is weak to Fighting... ARGH! 
Also his Alakazam, which is just plain fast and powerful. Kept KOing me before I could even get a hit in. I have a move which I'm pretty sure would OHKO it (U-Turn wielded by an Azelf), but I can't use it fast enough!
Level-grinding it is, then. I'm not reattempting this until my team's at level 55. Strategy can only get one so far... eventually, you need some brute force on your side as well.
If you have a lot of X Items, status/healing moves and medicine it is possible to take down the Elite Four at around level 50. Search for Marriland's Elite Four videos on YouTube.
If I can beat Lucian, I'll only have one Pokemon to truly worry about for the Champion: a level 66 Garchomp. Dragon/Ground combo with absurd Attack and armed with Earthquake, Dragon Pulse, and Giga Impact. I did make sure to have Ice Beam taught to one of my Pokemon... the only question is, will it be enough? 4x weakness is pretty good, but even at level 55 that's an 11-level difference, and Garchomp is among the most powerful non-legendary Pokemon in existance... 
I took all my Pokemon up to level 56 too (except for my Bastiodon, who had an EXP Share - I took him along because I taught him Blizzard), and I took them on and won in one shot. My team was Empoleon, Palkia, Staraptor, Bastiodon, Mesprit and Garchomp. I don't really remember too much about how well I did, thought. Sometimes it's better to have good defense rather then good offense. Remember, the last one standing wins. Also, make good use of held items (e.g. try and get a Wacan Berry or the one (I don't know its name) that weakens Ice attacks for your Flying Pokemon, or use something like a Shell Bell or Quick Claw), and a few X Items (if you're not doing the level 50 route) are useful too. Moves like Endeavor work great too if you're in a tight spot, just watch out for them using their Full Restores.
Now, Cynthia's Garchomp, like you said, is 4x weak to Ice, but remember that it also has a 2x weakness to Dragon also. That's why it's good to have another Garchomp or the mascot (Dialga or Palkia - however Palkia is much better since it's not weak to Ground OR Fighting (Her Garchomp's fourth move is Brick Break)), and use a powerful Dragon-type attack on it, such as Dragon Rush, Draco Meteor, Spacial Rend or Roar Of Time. I think that's what I did. If you're going to use Ice-type attacks, make sure the one that knows it can take a bit of punishment, because Garchomp is extremely fast, so you may get hit before you use Ice Beam or Blizzard.
Be careful with Cynthia's Spiritomb too, because it has no weakness at all (because it is Ghost/Dark) - however you can use a move like Odor Sleuth or an ability like Scrappy and remove its immunity to Fighting, allowing Fighting attacks to deal 2x damage to it.
Hope this helps.
