It's been a very long time since I've done any of this, and I don't think I have the time to get into it again. Hacker would probably be a better source of information now.
I think I used something like PE Explorer to increase the size of the data section. Maybe I'm wrong about the name, but it was easily found with Google and was free to use. There is a way to increase the size of the data section with it. I used it once on Outpost2.exe to insert a code patch at the end of the code section (I think). I don't think it cleared the memory to 0, but it did extend the file and moved the data from the next sections back a bit, so you'll probably notice data is duplicated in the area you've extended it. Maybe just clear the extended area to 0s and test to see if it still works first. If it does, start putting the new strings in there.
Once the new strings have been written in, you'll need to find the references to the old strings and update the addresses. This can be a little more tricky with just a hex editor though since the strings will be accessed through virtual addresses rather than file offsets. There is a way to convert between the two, but it might be easier to find the virtual addresses with a debugger. (W32Dasm, OllyDbg, IDA, etc.)
Anyways, find references to the old virtual address of the string and overwrite them with the new virtual address. (You might have to do the edit with the hex editor, but the debugger will help you find the right location). Just be careful if there are lots of references though since that number (the possible virtual address) might have other meaning not related to the string at all, so if you changed them it might cause crashes. In practice though, it's pretty rare that a random value just happens to represent a valid memory address, especially one that points to the start of a string. You might have to look in both the data and code sections for the references to the string. (Try the data section first, just in case you find a table of string pointers. That's usually a fairly sure bet and easy to understand).
Summary:
1) Find lcoation of the old string (VA - virtual address)
2) Find location of the new string (VA)
3) Find references to the old strings VA (Try data section first, then constants in the code section)
4) Replace the old VA with the new VA (probably with a hex editor). You may need to do a search of the bytes in the area you're overwriting to find it since the file offset won't match the VA exactly (but lower order bits are often the same). But hey any decent debugger will give you the code bytes alongside instruction mnemonics if you're doing a code edit.