A significant portion of Diane Duane's novel Spock's World
deals with events on pre-Federation Vulcan. In a way, it's like two books in one, since you can read the Vulcan stuff as a series of short stories without reading the 23rd century material, or vice-versa.
Other than that and what's already been mentioned, you might want to check out what's available in fanfic. There's plenty out there that involves the Federation (or other places known to the Federation) but isn't Starfleet-centric or uses all-canon characters.