Give execute permission to user which does not have execute permission for specific stored procedure
While a procedure runs, normally it has access to data in the database like the owner of the procedure, which is usually "dbo" and can access everything.  I may have got this wrong: I seem to be describing "EXECUTE AS OWNER" and I have documentation which says that the normal setting is "EXECUTE AS CALLER".  I just thought that is what a "procedure" was -for-.  Anyway, either is an option.

A procedure's references to objects in different databases use the rights of the actual user - they must do because a procedure only understands security in its own database.  An exception is where a user's connection invokes an "application role"; in that case, the user has the access of the "guest" account to objects in other databases.  This normally is or ought to be "no access".

None of this relates to who is allowed to execute a procedure in the first place, and that is what you're trying to set.  That has to be allowed with GRANT.

However, if you issue GRANT and DENY commands that apply to the same object access, the result is to DENY - that's absolute.  Perhaps you've made that mistake.  To un-grant privileges, use REVOKE when you don't want to DENY.  Also, normal practice is to GRANT or DENY privileges to roles, then manage which roles a user is a member of.  Or even roles with privileges, whose members are roles with business functions (job titles), whose members are actual user accounts.

What "EXECUTE AS" does is to control the object access rights that a user may be "given" (or denied) in a procedure which the user doesn't have in an ordinary batch of Transact-SQL commands.