How to alter HTML generated for $messages?
You just need to override the theme function...

theme_status_messages($variables)

https://api.drupal.org/api/drupal/includes%21theme.inc/function/theme_status_messages/7

function YOURTHEME_status_messages($variables) {
// code goes here...
}