What's the difference between non-standard and invalid?
Invalid transactions double-spend coins, try to redeem an output in such a way that the script returns false, or are formatted incorrectly. Invalid transactions are always rejected. One invalid transaction in a block chain makes all blocks after and including it invalid.
Non-standard transactions do something that the official client would never do. Usually they have scripts that are different from the two scripts that Bitcoin produces. Non-standard transactions will be accepted if they are seen in a block, though miners using the official code will not put them in blocks they mine or relay them to other miners.
Luke-jr's pool accepts all non-standard transactions if they pay a fee, so non-standard transactions are possible.
Can arbitrary data be stuffed into a transaction? If not, what are the limitations?
Yes. The transaction can (optionally) still be redeemable after doing this, too. Each script can be 10,000 bytes max, but each transaction can have an unlimited number of scripts. The max size of a block is 1MB, though, so a transaction larger than that cannot possibly be included in a block.
Need these be "transactions" at all in the sense of involving transfers between bitcoin addresses?
No. An output script sets the conditions under which the BTC contained in that output can be redeemed. A transfer to a Bitcoin address creates a script saying, "If you can sign data for this public key hash (address), you can redeem this output." But there are many different conditions you could set.
How do I go about creating a non-standard transaction?
You must modify Bitcoin. Stock Bitcoin will never create non-standard transactions.
What are some (actual or potential) use cases?
You could make a transaction redeemable for a password instead of a public key, or require multiple signatures (useful for escrow transactions).
See:
https://en.bitcoin.it/wiki/Script
