How to create a new public AMI for windows with a random password?

You could go to the EC2ConfigService Settings (Start -> all programs) on your instance. Under "Set Password" put a check in "Set a random password ....".

The password will be generated on next boot and your ami created from the instance will have a random generated password.

Alternatively you can edit your C:\Program Files\Amazon\Ec2ConfigService\Settings\config.xml file by setting Ec2SetPassword to enabled:

<Plugin>
  <Name>Ec2SetPassword</Name>
  <State>Enabled</State>
</Plugin>

And restarting the Ec2ConfigService (running as a windows service on the instance.)

After doing this you can create your ami in the usual way (shut down the instance and rigth-click on the instance -> "Create Image (EBS AMI)".