If you look back at suggested cat names, you will find that we had a beautiful Russian Blue female cat for 13 years - her name was Smudge! (When we first got her, she was a tiny little grey/blue smudge, hence the name).
Mishka was the name given to our first black cat. He was the most lovable and gentle cat we have ever had. My husband, who is Russian, named him because he was as cuddly as a little teddy bear! I have always loved the name.
I always liked the name Zhenya.Then again that is about as un-cute as Vladimir. What about Vova? Danu? Vanusha? Rasputin might be cool, it's a known name, and has a great story - if anyone asks you can tell them about Gregori Rasputin.