My question is how many more rounds would they have to use to keep this security margin on AES (other then adding a hash to AES 256 key schedule)?
When AES was standardized, the best known attack (pdf, page 19) in terms of rounds broken was a related key attack that broke 9/14 rounds of AES-256. The best attack on AES-128 broke 7/10 rounds.
Currently, the best attacks (pdf, paywall) are actually on full round variants. It's just that those attacks are only very slightly better than brute force. If you assume those attacks do not apply to increased-round variants, you would get the same security margin of unbroken rounds by defining AES-128 with 13 rounds and AES-256 with 19 – or maybe 14 and 20 for nicer numbers and in case an extra round can be broken with current attacks.
However, "rounds broken" is a rather crude measure. The best practical attack (in terms of computational cost) at the time of standardization was on six rounds for all variants. Now there are at least related-key attacks of practical complexity on 10/14 rounds of AES-256.
Either way, something like 14/20 rounds for AES-128/256 might be a reasonable number if the standard was revised, but attacks are still far from practical.
And would NIST actually change the standard again to something more secure such as Serpent?
I doubt they would just change it to another existing cipher. Serpent may have more of a security margin, but it has also seen less cryptanalysis at this point. More likely would be another competition for "AES-2", like the one for SHA-3. Existing ciphers might be submitted, of course, but new ciphers would also be considered.
