I would suggest trying to get your hands on a "Leaf" runeword. Its for 2-socket staves and only needs a tir and ral rune. Its very powerful at low levels giving you +3 to all fire skills, +3 warmth and +3 inferno/fire bolt. This helps greatly with mana regen and damage output and you can use it at level 19. If your starting fresh with no help this staff can easily take you through nightmare.
You will find a Tir before act3 more than likely and ral is also very common. You could easily find one by act 3-4 or you could try asking somebody for one. Save your gold and stop by the staff vendor whenever your in town. Anything with +fireball is good. Warmth, meteor or static field would be nice extras if you can find a staff with fireball and one of these skills.