Test before insert on Case created from Email-to-Case

You should be able to create an instance of your class that implements Messaging.InboundEmailHandler in the test method and then pass it a Messaging.InboundEmail and Messaging.InboundEnvelope. This will create the Case and associate it with the email.

E.g.

global class EmailToCaseHandler implements Messaging.inboundEmailHandler{ ... }


@isTest
private class EmailToCaseTest {
    static testMethod void testCaseFromEmail() {

        Messaging.InboundEmail email = new Messaging.InboundEmail();
        email.subject = 'test email-to-case';

        Messaging.InboundEnvelope env = new Messaging.InboundEnvelope();
        env.fromAddress = 'user@acme.com';

        EmailToCaseHandler emailHandler = new EmailToCaseHandler();
        emailHandler.handleInboundEmail(email, env);


        // Make assertions about the case that should be created.
    }
}

Maybe I misinterpreted what you were asking for... Do you just want to test a Case that is associated with a EmailMessage?

Here you would first insert the Case before inserting the EmailMessage. When inserting the EmailMessage, use the Case.Id field to populate the EmailMessage.ParentId field.

How can you find the EmailMessage that is associated with the Case via the EmailMessage.ParentId when the Case is being inserted.

My answer here is that you can't. The EmailMessage is inserted into the database after the Case is because it needs to reference the Case.Id in the ParentId field. See Trigger on Case EmailMessage

Process builder!

As of Spring '15 you can use the Process Builder for cool stuff like this.
Setup > Create > Workflow & Approvals > Process Builder

Previously this would have had to be done using APEX. I believe you would have to do something similar to what's being shown below in the Process Builder - create a new Task (not update the automatic one) since there's no real link between the EmailMessage record and the Task created from it.

Make sure you turn off the automatic Task creation for this routing address in the Email2Case settings or you'll get a duplicate.

Basically, when an Email Message comes in where IsInbound = True, create a task, relate it to the Case, set the Type, etc....

good luck!

quick note:
I had a problem the first time I tried this where the email bounced back to the sender with an ugly error. This is because Cases in my org are owned by a Queue and I tried to set Assigned To ID to the Case Owner. Since it wasn't a User, it wouldn't work. You can specify any User such as the Account.Owner. I used EmailMessage.CreatedBy. That just uses the automated workflow user I think.

"Unhandled process fault" 
caused by element : FlowRecordCreate.myRule_1_A1
caused by: UPSERT --- UPSERT FAILED --- ERRORS : (FIELD_INTEGRITY_EXCEPTION)     
Assigned To ID: id value of incorrect type: 00G30000002SjhQEAS --- for SFDC record with ID : null,

Name ID on the Activity might be problematic as well. You could use the parent Case's Contact field but that might either not be set, or could be someone different than the actual sender.

Make sure whatever you do that no Process Builder, Workflow, Validation, APEX errors will prevent emails from being processed.