After clearing the plan cache on SQL Server, how do I regenerate execution plans for stored procedures without executing the stored procedures themselves?
You don't / can't. Execution plans are generated when the object is executed. If you want a plan in the plan cache, then the object must be executed. BUT, assuming that there is at least one input parameter to the stored procedure, you would need to use a value that represents probably the majority case, else you could be forcing a non-ideal / "bad" plan into the cache.
if I have to do this again, I'd like to avoid the performance hit from regenerating the plans while a user is waiting for a response.
You are better off taking the performance hit because you can't guarantee that the plan will even still be in the cache by the time the first person uses it. Plans can be dropped if SQL Server decides that it needs more memory for other operations. So if it does get dropped before the first person uses it, you saved them nothing, and now caused the server to generate the plan twice.
Besides, it is only a hit the first time. You are aware of this as you are trying to use it to your advantage in "pre"-caching it. But this also means that it will only be the first user that first time that gets a slight performance hit. After that, as long as the plan isn't dropped, others wouldn't be experiencing the performance hit anyway.
Save yourself a lot of wasted time / effort and don't worry about pre-caching. Worry more about performance problems with the queries in the stored procedures that would affect all users each time and spend your time wisely improving those trouble spots.