Define Campaign Member Status via Apex?

I do not see any problem to change it with Apex using CampaignMemberStatus standard object. You should have an campaign ID for that:

CampaignMemberStatus ms = new CampaignMemberStatus();
ms.CampaignId = '701E0000000K21v';
ms.Label = 'New Status';
ms.SortOrder = 5;
insert ms;

Here is the table campaignMemberStatus and fields you can update. It is available via data loader (I can't remember but you may need to allow all objects). It is also available in apex and treated just like any other object.