Araca Azul by Caetano Veloso is fucking nuts and utterly brilliant. Kinda like a tropical Faust. None of his other albums come anywhere near being as weird.
The French band Lard Free are very krauty and not very well known. Don't be put off by the name, they're worth checking out. Same goes for Heldon, though they're more Fripp/Eno influenced than anything else, but should appeal to krautheads.