After Effects will be more suited to the task than Premiere.
No easy way so you will have a bit of learning to do if you want a custom effect.
You may need to decide exactly what you want before you start though.
Big difference between a "Type on Effect" and "Text with fire" emitting from it.
There are lots of After Effects comps available on the Internet that might do what you want.
Take Video Blocks for example. You can get a free trial for seven days. During those seven days you can look through and see some of the title sequences they have just waiting for you to make your changes and use. Either as is, or with changes that make it your own.
Besides the great suggestions so far, you might want to look into a couple of 3rd party programs:
BluffTitler (I think that it has a "fire" Effect as a Preset, and does have "Typewriter")
ProDAD's Vitascene, along with their Heroglyph
Pixelan's Spice Master (more for Transitons, but you can create custom Effects too)