Warum nimmst du dir nicht das telefonbuch.de kombinierst häufige Namen mit beliebigen Städten und hast dann auch die Adresse. Namen, Vornamen und (Adresse, Stadt) kannst/solltest du dann beliebig randomisieren.
Die Suchanfragen bei telefonbuch.de werden über die
URL übermittelt, das parsen nach den Einträgen ist auch recht einfach.