You're right to be against the subdomain idea - that's not a good call for SEO at all.
What I would do is start out with a full database export of all the URLs on the current site, and figure out what URL each of those resources is ultimately going to live at. This can be daunting with a large site, but it goes faster than you think it's going to - once you figure out that all the pages in example.com/old-folder/pagename are now going to live at example.com/new-folder/pagename you can figure out the URL structure for large chunks of the site at a time. Since it sounds like there won't be any changes to the overall design and structure of the site, just some possible URL changes, that will make it easier, too. I did this for the SEOmoz.org -> Moz.com transition and it took about a month to map out 65,000 pages alongside my other SEO duties (but that was with a lot of major changes in site structure, too).
Once everyone (you, the client, both dev teams) have agreed on the new structure, it's simply a matter of:
- moving the pages in each "chunk" from their old URLs to their new URLs
- 301 redirecting the old URLs to the new URLs on a page-to-page level
- doing a database find+replace on the old site and the new one to update internal links to those pages
Be really really careful with managing expectations for this. It's very common to see pages take a temporary hit in rankings and traffic immediately after they move to a new URL; this drop is usually temporary and reversible. But you don't want the client taking that data as proof that the migration isn't going to work or isn't working, and abandoning ship. To help matters along, take a look at what their best inbound links are and the linking sites with whom you have the best relationship, and as those pages move to their new addresses, reach out to the linking sites to try to get those links updated.
Does that answer your question? Happy to discuss further if not.