I need to append a meta data to each message when publishing to the queue. The question is which method is more efficient?  

Add custom fields to every message body
Add custom headers to every message

Just in case:

Publisher is on AWS m1.small
Messages rate is less than 500 msgs/s
Rabbit library: pika (python)
Efficiency in terms of speed, there is probably no answer to your question, since there are efficient parsing methods available to extract the meta data from your messages after they leave RabbitMQ.
But in case of using the meta data to filter your messages, it would be more efficient to do that in RabbitMQ, since you can do that filtering inside of RabbitMQ by using header exchange.
What is more efficient: add fields to the message or create a custom header? RabbitMQ