Can natural language generation algorithms generate valid words too?
Outside of context of NLG (thus not a direct answer to your whole question, but an answer to your question's title): Generating words from a character-level model has been done using RNNs exposed to large corpora of text, such as Wikipedia content, and trained to predict text character-by-character.

Used to generate content, the model is normally fed a few starting characters and asked to predict the next one. A choice is made from its most-likely predictions and fed back to it to continue the sequence. 

Here is a blog showing some examples trained on some Shakespear and Wikipedia.

Such a network can and does generate nonsense words, although they are often fitting and might read like e.g. a noun or verb as you could expect depending on context. The sentence structure and grammar can come out sort of right, but the semantic content is usually complete gibberish.