Maybe something like this would work? (I don’t have a Python interpreter in front of me, unfortunately)
from bs4 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")
result = str(soup)