GRANT EXECUTE to all stored procedures

SQL Server 2008 and Above:

/* CREATE A NEW ROLE */
CREATE ROLE db_executor

/* GRANT EXECUTE TO THE ROLE */
GRANT EXECUTE TO db_executor

For just a user (not a role):

USE [DBName]
GO
GRANT EXECUTE TO [user]

SQL Server 2005 introduced the ability to grant database execute permissions to a database principle, as you've described:

GRANT EXECUTE TO [MyDomain\MyUser]

That will grant permission at the database scope, which implicitly includes all stored procedures in all schemas. This means that you don't have to explicitly grant permissions per stored procedure.

You can also restrict by granting schema execute permissions if you want to be more granular:

GRANT EXECUTE ON SCHEMA ::dbo TO [MyDomain\MyUser]