Be careful of assigning db_ddladmin for the purposes you've described. It will give the users permission to manipulate object definitions (tables/views/SPs), but not the execute permissions you require.

Unfortunately SQL doesn't have a db_ExecuteAnyUserProcedure role. You need to grant execute rights on each stored proc.

The public execute permission problem is a weird one. Often seen it for other users because SID mismatches after restoring on another server, but it (theoretically) shouldn't happen for PUBLIC.