Is there an app that would help me translating words from Russian to English when I travel? Ideally I would make a picture and it would translate it for me, but I'd be happy with an app that let me insert Cyrillic chars and it shouldn't use any data services.
So, what you are looking for is an offline Russian-English (and probably English-Russian) dictionary? I have a Samsung Focus device and there is a free Russian-English-Russian dictionary app from Samsung (featuring a Langenscheid Dictionary) available for this device. The dictionary is not very large, but it is OK for my needs. If you search for Russian-English dictionaries in the App Market you'll find some free and paid application which claim they don't require internet connection.
Bing Translator may fit your needs. It uses offline language packages so you do not need data services (except for downloading the Russian Language Package, of course! ;-) ).