So, first, you're probably better off using ssh keys to gain access to your instances, rather than passwords. This avoids the need to generate or modify passwords, while still allowing you to access your instances immediately.

With that out of the way...

When you boot a Nova instance (with or without Heat), you can provide a blog of user-data that is available to the instance through the Nova metadata service. Cloud-enabled images from most vendors (Fedora, Ubuntu, RHEL, CentOS) run a program called "cloud-init" when they boot that queries this user-data and can use it to perform initial boot configuration tasks. In the simplest case, the user-data can just be a shell script.

You can provide a nova instance with a user-data script in your Heat template, as in this example:

myserver:
  type: OS::Nova::Server
  properties:
    image: { get_param: image }
    flavor: { get_param: flavor }
    key_name: { get_param: key_name }
    networks:
      - port: { get_resource: controller_port }
    user_data_format: RAW
    user_data: |
      #!/bin/sh

      echo Hello world > /root/bootup.log

This script doesn't do anything other than echo a line to a log file, but you can do anything you want here. Heat also has the ability to generate random strings for you, through the OS::Heat::RandomString resource:

root_pw:
  type: OS::Heat::RandomString

And, heat has the value to perform some basic token replacement on text. You can use this feature to (a) have heat generate a random string, (b) subsitute it into a user-data script, and (c) assign that random string as a password. Something like this:

resources:
  root_pw:
    type: OS::Heat::RandomString

  myserver:
    type: OS::Nova::Server
    properties:
      image: { get_param: image }
      flavor: { get_param: flavor }
      key_name: { get_param: key_name }
      networks:
        - port: { get_resource: controller_port }
      user_data_format: RAW
      user_data:
        str_replace:
          template: |
            #!/bin/sh

            ROOT_PW="@ROOT_PW@"
            (
            echo "$ROOT_PW"
            echo "$ROOT_PW"
            ) | passwd --stdin root
          params:
            "@ROOT_PW@": {get_resource: root_pw}

outputs:
  root_pw:
    value: {get_resource: root_pw}

You could obviously extend the script to generate a new user, configure sudoers, and set a password on that account.