There are some excellent balance exercises in one of Loren Christenson's books, Solo Training---LC is a very good, no-nonsense writer, with major expertise and knowledge (from a Karate perspective) whereof he speaks, and the whole book is full of terrific exercises for strength, accuracy, fluency of motion and the other requirements for competence in MA. Another good one is Sang Kim's Martial Arts after 40---he's coming to it from TKD and Hapkido---some very good exercises aimed at improving coordination, which is intimately connected to balance.
For developing balance in kicking---probably the toughest test of balance, by its very nature---a very good, very tough exercise is to do each type of basic kick very slowly, in perfect form. One of the things makes this hard is that when you kick at normal speed you typically use the momentum of the kick to power your smooth pivot on the balance leg. When you do the kick slowly, that's not gonna happen, but you're asking yourself to do the pivot smoothly anyway. If you work persistently on that particular exercise for rear leg side kick, turning kick and back kick, you'll find your balance skills will increase dramatically over a three-four month period. Try slowing the kick down, and when you get it right, slow it down more, and so on, till you can freeze at any point in the kick and maintain it for fifteen seconds in correct form.
It really works but it's bloody tough---keep a chair handy nearby to grab onto!