I just did this earlier today. I downloaded the most popular firstnames and lastnames from some website... so they're in their own tables. Then I did this (appended a partial cross join to a final table):
INSERT INTO Training.dbo.Technician (FirstName, Gender, LastName, StartDate, StoreID)
SELECT TOP 4000 f.FName
, DATEADD(day,-1 * ABS(CHECKSUM(NEWID())%(15*365)),GETDATE()) AS StartDate -- a start date some random # of days ago
, ABS(CHECKSUM(NEWID())%100) AS StoreID
FROM Scratchpad.dbo.FirstNames f CROSS JOIN Scratchpad.dbo.LastNames l
ORDER BY NEWID();
The ORDER BY NEWID() basically randomizes the order, and then the TOP predicate just selects some of the results. It's pretty slow, but I only needed to run it once.