"hard to implement," yes. "really awesome if it works," also yes.
This may not be the thread to discuss feasibility of procedural history.. but here are some links to tangentially-related articles:
* gamedev subreddit
provides a lot of useful links
* 'Game Forge' language
to "integrate story and world"
* Procedural Puzzles And Plot Generation
has a brief intro and more links.
But, maybe the "story" can be more loosely defined than all that.. One of the most important points in all of this is, I think, "human imagination will create a plot out of a sequence of events without necessarily having an underlying plot" (from the 3rd bullet).
Maybe it's much simpler than all this if we know beforehand what set-points there are in Trillek history, then it's just a matter of pairing scripted events with generated locations (and, as you said, not giving everything away).