They mean different things. "I taught myself to believe every story I was told " means that the speaker came to believe every story that someone else told him, as you say. "I taught myself to believe every story I told " means the speaker told stories, implied to be stories that were not true or not entirely true, but came to believe (or pretend) that the stories actually were true.
New words, one handy idiom, and a 2-minute quiz — delivered to your inbox to keep your streak alive.