I use the Bucket Blaster (from MoreBeer) to clean my kegs. Has tubing to connect to ball locks (includes the QD's for them) to clean inside the tubes as well. I fitted mine with a CIP ball (1/2" NPT connected). With the heavy coating inside your keg, I'd at least start with a full fill of strong (hot) PBW and move on from there. Get it as full as possible, and make sure the dip tubes are also fully submerged (make sure fluid goes inside them).
I have yet to need to clean with anything besides PBW. Depending on how stubborn the stuff in your keg is, you might need something stronger. Or just a couple of soaks. You can also use a dish brush (I'd never recommend a toilet brush, no matter what). IME, a dish brush should be long enough to get full depth, with your arm inside the keg opening. Unless you have thick arms. Pull at least the liquid dip tube out before you do that, so that you can get everywhere easily. Depending on your reach, you could also try some BKF (Bar Keepers Friend) inside.
Just be sure to give a complete rinse for whatever you use to clean.