How do you use the LuckPerms pluginmsg messaging feature?

I have LuckPerms on all of my servers and the proxy, and I have the messaging services all set to pluginmsg, but it still doesn't work.

What is your storage type?
This will only work, if all instances of LP share the same database (MySQL, MariaDB, etc.)
It won't work with file-based storage-systems (yaml, json, ...) or the default H2 storage.

Also you can use the default sql messaging service, when using a MySQL-like database (This is default when MySQL or MariaDB are used)

I don't have an available MySQL database. Is there a way I can use a messaging service without one?

No.
Since the messaging service only tells the other LPs to refresh their cached data from the database.
And since files won't be updated accross servers, this wouldn't change anything.