How can I grant permission to API Gateway to invoke lambda functions through CloudFormation?

There is a CloudFormation solution to this problem. See the following CloudFormation snippet:

"Permission": {
    "Type": "AWS::Lambda::Permission",
    "Properties": {
        "FunctionName": { "Fn::GetAtt": [ "Lambda", "Arn" ] },
        "Action": "lambda:InvokeFunction",
        "Principal": "apigateway.amazonaws.com",
        "SourceArn": { "Fn::Join": [ "", [
            "arn:aws:execute-api:",
            { "Ref": "AWS::Region" }, ":",
            { "Ref": "AWS::AccountId" }, ":",
            { "Ref": "API" },
            "/*/*/*"
        ] ] }
    }
}

This grants API Gateway permissions to launch your Lambda function. Variables in this snippet you need to change are Lambda (line 4) and API (line 11).

For the invoke permissions:

    "APIInvokePermission": {
  "Type": "AWS::Lambda::Permission",
  "Properties": {
    "FunctionName": {
      "Ref": "YOUR_LAMBDA_FUNCTION_RESOURCE_NAME"
    },
    "Action": "lambda:InvokeFunction",
    "Principal": "apigateway.amazonaws.com",
    "SourceArn": {
      "Fn::Sub": "arn:aws:execute-api:${AWS::Region}:${AWS::AccountId}:${YOUR_REST_API_RESOURCE_NAME}/*/*/*"
    }
  }
},