I hope the real story isn't in all caps 
Uuuhm... You don't think the story is in caps because we like to shout, do you? 
You could also just write it with proper use of capitals, and later on count how many capitals you've actually used.. if it's just 8 or so, then you could probably tuck away 8 caps chars in some corner of your tileset..
Apart from the fact that having a nice and readable lowercase font in just 8x8 pixels is quite a PITA
I guess you don't need a full tileset when telling the story...
That's right...just tell the story with some cutscenes and some pattern-fading-special-effect where you load a prearranged tileset of text each time...
that's what I do for KM3...and I use real gothic-font-type...very pretty !!
You probably could leave out the either case of the letter 'Q'. Now don't come bite me in the bum because you had a Q in the text. I hate those things. I never read them, unless they're in a proper demo[tm] 
Some bosses/characters in the scenario have got Amharic names like "Masnaq Tares" and the general 'black magic' power in the story is called "T'qur Asmat"...