I have used cart attributes since they were introduced, and found most of the bugs associated with them along the way (which Shopify fixed along the way), giving me enough confidence to inform you on this question.
To edit them, simply provide the cart with the same key you used to create them, and change the information. If you provide an empty value, you'll remove the key. It is just a key:value store. As are line items, which by the way, are editable in my book. I managed to edit them by simply changing the value of the key, and by providing the line item index value, something maybe you overlooked?
Anyway, if you take the provided Shopify Javascript API code, and examine that small library, you'll see the functions used to create attributes. With a little minor change, you can introduce your own cart attribute CRUD functionality to suit your needs.
Here is an old example showing off updating the cart attributes, data is a string ie) "attributes[fizz]='buzz' (and note that you can thus store JSON):
updateCartAttributes: function(data, callback) {
var params = {
type: 'POST',
url: '/cart/update.js',
data: data,
dataType: 'json',
success: function(cart) {
if ((typeof callback) === 'function') {
callback(cart);
}
else {
Shopify.api.onCartUpdate(cart);
}
},
error: function(XMLHttpRequest, textStatus) {
Shopify.api.onError(XMLHttpRequest, textStatus);
}
};
$.ajax(params);
}