Fortunately Python is very good with text manipulation. All you need to do is the "lstrip" string method (to cut off a specified character of the left side of the text string):
address = "000718 Puget St. SW"
newAddress = address.lstrip("0")
print newAddress
'718 Puget St. SW'
In a Field calculator expression, it would look like this:
gp.CalculateField_management(myFC, "NEW_ADDRESS", "!FUBAR_ADDRESS!.lstrip('0')", "PYTHON")
or you feel invincible, you could overwrite the existing field:
gp.CalculateField_management(myFC, "ADDRESS", "!ADDRESS!.lstrip('0')", "PYTHON")