Here's another option

with sampleData as (

SELECT FirstName, LastName, ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) N

FROM (VALUES

('Robin','Bacon'),

('Owen','Twomey'),

('James','Kendall'),

('John','Cavanagh'),

('Lola','Oxborough'),

('Thomas','Archibald'),

('Mathias','Kearns'),

('Christine','Winger'),

('Barry','Kane'),

('Rereahu','Gray'),

('Douglas','Christian'),

('Jennifer','Clark'),

('Kenneth','Court'),

('Paul','Pedersen'),

('Bruce','McKelvie'),

('David','McCrary'),

('Paul','Allison'),

('Linda','Cawthorn'),

('Noelene','Schellhorn'),

('Patricia','Pedersen'),

('Ivan','Hill'),

('Stewart','Leys'),

('James','Austin'),

('Roger','McManaway'),

('Katherine','Edmonds'),

('Bryan','Wilson'),

('James','Jones'),

('William','Healey'),

('Caroline','Rae'),

('Stephen','Mullins'),

('Graeme','Gray'),

('Gary','Gibbens'),

('Annie','Oxborough'),

('Emma','Kennedy'),

('Patricia','Wii'),

('Raymond','Winger'),

('Judith','Owen'),

('Ruby','McCrary'),

('Peter','Waterhouse'),

('Gaye','Cox'),

('Barbara','Hill'),

('Jeanette','Patchett'),

('Norman','Forbes'),

('Andrew','Forsyth'),

('Aldyth','Edmonds'),

('Mick','Stohr'),

('Nicola','Howie'),

('Linda','Gray'),

('Fenella','Silva'),

('Allan','McCandless'),

('Gillian','Scott'),

('Garth','Woodcock'),

('Peter','Woodcock'),

('Fenella','Waterhouse'),

('Patricia','Leys'),

('Paul','Sykes'),

('Richard','Fortzer'),

('Dean','McKelvie'),

('Cuan','Fortzer'),

('Vaughan','Heymons'),

('Donald','Toseland'),

('Alan','Sclater'),

('Nancy','Ollerenshaw'),

('Eddie','Buhler'),

('Lewis','Taylor'),

('Kerin','Medland'),

('Carlton','Forsyth-King'),

('Opie','Cleland'),

('Gail','Oshannessy'),

('Stuart','Gray')

) AS N (FirstName, LastName)

)

,RandFirstName AS (SELECT FirstName, ROW_NUMBER() OVER (ORDER BY RAND(CAST(NEWID() AS VARBINARY))) N FROM sampledata a)

,RandLastName AS (SELECT LastName, ROW_NUMBER() OVER (ORDER BY RAND(CAST(NEWID() AS VARBINARY))) N FROM sampledata a)

SELECT f.FirstName, l.LastName, a.FirstName, a.LastName

FROM sampledata a

INNER JOIN RandFirstName f ON a.N = f.N

INNER JOIN RandLastName l ON a.N = l.N;

Sample data was pre randomized, but it still came up with a name of someone I know:-) Fortunately he wasn't in the original list.

Edit: Just tested this over around 500,000 rows and had it return 1 or 2 non randomized names 6 out 10 times. They were generally common names though, eg John Smith