Privet :) Is there any app or webiste where I can talk with native russian speakers for free? With talk I mean really talk and not just write.
vk.com for one. It's a Russian Facebook clone which many people use as a Tumblr substitute (yours truly included). If you find someone you want to talk to, just exchange Skypes.
As to how to find talking partners, just browse the 'groups' ("Группы") and either search for English learners (then it'll be mutually beneficial), or for groups centred around your interests.
Also, don't be afraid to talk to girls just because they're girls (as a certain user suggested). That's sexist.
And if, by any chance, you're interested in anime/manga, Doctor Who, cats, or Java/Android programming, you can talk to me ;)
I use Interpals. You can find people who actually learn language by using filter.
http://italki.com - there you can find Russians willing to have a language exchange speaking practice (normally it is 30 min in Russian and 30 min in your language, but not necessary). Also you can find a community tutor there (informal teaching) and teachers of Russian.
Good luck with learning Russian!