String templating technique
Custom columns {{shudder}}. 

There's not One True Way® that comes to mind, but what about one or more rows in the new UserNotificationMetadata table, which has a MetaKey VARCHAR(x) not null (with a small but practical "x")  and primary key of (NotificationId,MetaKey) and a MetaValue TINYTEXT not null (or a comparably suitable data type)?

This is one of the relatively few cases where a sort of EAV-style structure is arguably not a case of urDoinItWrong™ since the data, here, isn't part of your core schema and there's (again, arguably) not a need to be able to impose constraints on the data... a number or date stored here is just a string of characters that's going into a message.  

For each (yes, that is also a little bit procedural-sounding) row matching the UserNotification, take CONCAT('{{',MetaKey,'}}') and use REPLACE() to substitute it with MetaValue in the message.

I would also suggest that 'seen' should be a timestamp, rather than a boolean.