Mysql – What permissions do I need if database a contains a stored procedure that inserts into a table in database b (same machine)

One only needs to ensure that the SP and objects that the SP accesses all have the same owner (ownership chaining rules)--then SQL Server doesn't look at permissions of chained objects. From the online SQL Server documentation:

Stored procedures take advantage of ownership chaining to provide access to data so that users do not need to have explicit permission to access database objects. An ownership chain exists when objects that access each other sequentially are owned by the same user. For example, a stored procedure can call other stored procedures, or a stored procedure can access multiple tables. If all objects in the chain of execution have the same owner, then SQL Server only checks the EXECUTE permission for the caller, not the caller's permissions on other objects. Therefore you need to grant only EXECUTE permissions on stored procedures; you can revoke or deny all permissions on the underlying tables.

The way that works best for me, to write stored procedures that execute dynamic SQL, is by not using "EXEC sp_executesql" when I start writing the stored procedure, but by using "PRINT" statements.

I make sure I get to see each and every SQL that the stored procedure generates. I copy them from the Messages tab and execute them from within Management Studio. Only after all SQLs work as intended, I allow my stored procedure to "EXEC sp_executesql" (instead of simply PRINTing the SQL statements).

Debugging works very fast this way. The most problems I encountered so far, are the result of missing spaces, like 'FROMMyTableName' or 'WHEREId = 12'.

You will have to test this as the certificate user or with an account that has similar rights. And if you can avoid using dynamic SQLs, avoid them.