Your first assumption is reasonable. Each thread should have its own connection.
As for the second point, the access to the DB that contains the new messages should be synchronized. For example, you can access that DB by a synchronized method that fetches a message or several messages that haven't been processed yet, and marks them as being processed. Two threads can't access that method at the same time, and therefore won't get the same messages.
Another option is to put the messages in memory in a blocking quoue (with the DB only serving for backup in case of a crash). The threads can request an item from the queue, which would block them until an item is available.