I am not completely sure from your description which parts you want to be persistent and which to be client-specific.
If you build markup and stylesheet from scratch for every client and don't use much custom PHP - there isn't much left for parent theme to do here. If you do use some custom PHP in each project - it might make sense to just put together our own parent theme.
Overall the generic process is to look through parent themes / frameworks until (if ever) you find the one you like. See WordPress frameworks and parent themesWordPress frameworks and parent themes.