Although this most likely breaks Google's TOS, you can scrape the autocomplete data easily:
import requests
import json
def autocomplete(query, depth=1, lang='en'):
if depth == 0:
return
response = requests.get('https://clients1.google.com/complete/search', params={
'client': 'hp',
'hl': lang,
'q': query
}).text
data = response[response.index('(') + 1:-1]
o = json.loads(data)
for result in o[1]:
suggestion = result[0].replace('<b>', '').replace('</b>', '')
yield suggestion
if depth > 1:
for s in autocomplete(suggestion, depth - 1, lang):
yield s
autocomplete('a', depth=2)
gives you the top 110 queries that start with a
(with some duplicates). Scrape each letter to a depth of 2, and you should have a ton of legitimate queries to choose from.