Using AWS CloudFormation to deploy an edge lambda

deploy.sh

#!/bin/sh

aws cloudformation deploy \
  --template-file stack.yaml \
  --stack-name edge-lambda-test \
  --capabilities CAPABILITY_IAM \
  --parameter-overrides Nonce=$RANDOM

stack.yaml

AWSTemplateFormatVersion: '2010-09-09'

Parameters:
  Nonce:
    Type: String

Outputs:
  Host:
    Value: !GetAtt Distribution.DomainName

Resources:
  Bucket:
    Type: AWS::S3::Bucket

  Distribution:
    Type: AWS::CloudFront::Distribution
    Properties:
      DistributionConfig:
        Enabled: true
        Origins:
        - Id: !Ref Bucket
          DomainName: !GetAtt Bucket.DomainName
          S3OriginConfig: {}
        DefaultCacheBehavior:
          TargetOriginId: !Ref Bucket
          ForwardedValues:
            QueryString: true
          ViewerProtocolPolicy: redirect-to-https
          LambdaFunctionAssociations:
          - EventType: viewer-request
            LambdaFunctionARN: !GetAtt IndexLambdaVersion.FunctionArn

  IndexLambda:
    Type: AWS::Lambda::Function
    Properties:
      Role: !GetAtt IndexLambdaRole.Arn
      Runtime: nodejs6.10
      Handler: index.handler
      Code:
        ZipFile: |
          exports.handler = (event, ctx, cb) => {
            const status = '200'
            const headers = {
              'content-type': [{
                key: 'Content-Type',
                value: 'application/json'
              }]
            }
            const body = JSON.stringify(event, null, 2)
            const response = {status, headers, body}

            cb(null, response)
          }

  IndexLambdaRole:
    Type: AWS::IAM::Role
    Properties:
      AssumeRolePolicyDocument:
        Version: '2012-10-17'
        Statement:
        - Effect: Allow
          Principal:
            Service:
            - lambda.amazonaws.com
            - edgelambda.amazonaws.com
          Action: sts:AssumeRole
      ManagedPolicyArns:
      - arn:aws:iam::aws:policy/service-role/AWSLambdaBasicExecutionRole

  IndexLambdaVersion:
    Type: Custom::LatestLambdaVersion
    Properties:
      ServiceToken: !GetAtt PublishLambdaVersion.Arn
      FunctionName: !Ref IndexLambda
      Nonce: !Ref Nonce

  # Custom resource for getting latest version of a lambda,
  # as required by CloudFront.

  PublishLambdaVersion:
    Type: AWS::Lambda::Function
    Properties:
      Handler: index.handler
      Runtime: nodejs6.10
      Role: !GetAtt PublishLambdaVersionRole.Arn
      Code:
        ZipFile: |
          const {Lambda} = require('aws-sdk')
          const {send, SUCCESS, FAILED} = require('cfn-response')
          const lambda = new Lambda()

          exports.handler = (event, context) => {
            const {RequestType, ResourceProperties: {FunctionName}} = event

            if (RequestType == 'Delete') return send(event, context, SUCCESS)

            lambda.publishVersion({FunctionName}, (err, {FunctionArn}) => {
              err
                ? send(event, context, FAILED, err)
                : send(event, context, SUCCESS, {FunctionArn})
            })
          }

  PublishLambdaVersionRole:
    Type: AWS::IAM::Role
    Properties:
      AssumeRolePolicyDocument:
        Version: '2012-10-17'
        Statement:
        - Effect: Allow
          Principal:
            Service: lambda.amazonaws.com
          Action: sts:AssumeRole
      ManagedPolicyArns:
      - arn:aws:iam::aws:policy/service-role/AWSLambdaBasicExecutionRole
      Policies:
      - PolicyName: PublishVersion
        PolicyDocument:
          Version: '2012-10-17'
          Statement:
          - Effect: Allow
            Action: lambda:PublishVersion
            Resource: '*'

Has @haydenk points out, just adding a new AWS::Lambda::Version works, and it's actually practical because you can remove the previous AWS::Lambda::Version in the same update, making it compatible with continuous deployment. Also the AutoPublishAlias is only available for SAM not CloudFormation.