You could do an Offer HN I'll help you come up with a name?
The other thing to do would be just to have a gentleman's agreement where they sign something (TBH I wouldn't worry with a legal contract initially, if you work with honest customers the gentleman's agreement is OK, and worst case if it was a big deal you could take to court and likely win)
So the agreement would be something like:
I'll come up with a name for you, I won't make you pay upfront, but if I come up with one you like and you haven't already thought of it [make them list all the ones they are currently considering upfront], then you'll pay me $500.
Reply to this email with your full name if you agree.
And then just make sure you follow them on twitter and connect on linkedin or such so that they feel that you would notice if they screwed you over, but like I say I think most people are nice and worrying about getting screwed over is likely premature optimization :-)
I'm fairly good at coming up with names, and wouldn't mind offering my services, but I'm not sure how to secure my idea before selling it.
I would also be open to testing my skills for anyone looking for a company name.