from BeautifulSoup import BeautifulSoup
soup = BeautifulSoup('<p>Blah blah blah <a href="http://google.com">Google</a></p>')
for a in soup.findAll('a'):
a['href'] = a['href'].replace("google", "mysite")
print str(soup)
Это решение Лусида, но, поскольку перед ним не было интерпретатора Python, он не смог проверить его, и в нем было несколько ошибок. Я просто хотел опубликовать рабочее состояние. Спасибо, Лусид!