This may not be the most efficient way, but it would map a unique C.message to every (A, B) assuming count(C) >= count(A, B).
SET @i:=0;
SET @J:=0;
SELECT ab_mapping.city, c_index.message
FROM (SELECT B.city, @i as ind, @i:=@i+1
FROM A JOIN B
ON A.b_id = B.id) as ab_mapping
JOIN
(SELECT c_rand.message, @j as ind, @j:=@j+1
FROM (SELECT * FROM C ORDER BY RAND()) as c_rand) as c_index
ON ab_mapping.ind = c_index.ind;
How it works
This sub-query assigns a unique integer (0 <= i < count(A, B)) to (A, B) mapping:
SELECT B.city, @i as ind, @i:=@i+1
FROM A JOIN B
ON A.b_id = B.id;
This sub-query assigns a unique integer (0 <= j < count(C)) to every message (in random order) in C:
SELECT c_rand.message, @j as ind, @j:=@j+1
FROM (SELECT * FROM C ORDER BY RAND()) as c_rand;
The final query joins both sub-queries on ind to assign a unique random message to each (A, B).