Hirut Beqele was widely considered the first lady of Ethiopian swing/r&b/rock/whatever back in the late 60's/early 70's. She is amazing, if the Ethiopian way of singing doesn't put you off. It's very, umm...sharp, and might sound a bit tuneless upon initial exposure.
Rita Abadzi recorded up until around WWII in the rembetika style (Greek folk music with heavy Turkish influence). R. Crumb loves her, and that's good enough for me! Seriously, this is powerful stuff.
Yanka Dyagileva recorded mostly solo acoustic material as well as material with her own group, Great October, and other groups like Communism and Survival Instructions. In Russia, she is considered something of a punk legend (having recorded during the CCCP period), although most of her connection to punk rock is through her association with Egor Letov of Grazhdanskaya Oborona (Siberian punk legends of the communist era), and his meddling in some of her albums. I doubt she would sound very punk to most people outside of eastern europe, anyway. She committed suicide by drowning in the Volga in 1991, but luckily all of her albums have been re-released on CD, as well as many live recordings. Check her out. Her music has a very unique atmosphere. Very russian, I guess.
I know these are kind of weird recommendations, but I noticed you had a non-english subcategory included in the initial post, which really does open things up a bit. I have music by these artists, if you can't find it/don't know where to look.
