Certificates, can they be generated on the fly, without access to a CA?
For proper SSL, the client must make sure that it talks to the right server, not a fake server operated by the attacker. This requires that the client knows the server public key. The certificate is a method for offering this guarantee: the server certificate contains the server public key, and the certificate is signed by the CA. The client knows the CA public key, and thus can use it to verify the signature on the certificate, and thus gain some confidence in the veracity of the purported server public key.
If you can hardcode a copy of the server public key directly in the client, then you can skip the certificates (maybe sending a dummy certificate to keep the client library happy). This is rather inflexible in practice, e.g. if you need to change the server public key, you then have to modify all the clients.
Therefore, it is often considered a better method to actually have a CA. You can operate your own CA; be sure to guard it well (physical security is important; 95% of CA management is procedures and guards and dogs). EJBCA is an open-source software that can help in running a CA. Alternatively, buy certificates from a commercial CA: this could be a good deal since it will save a lot of time on your side.
You could generate certificates on-the-fly (traditionally "self-signed") but such an automatically generated certificate does not prove anything -- anybody can make a self-signed certificate with arbitrary contents, at any time.
Certificate expiration - is there a limit to how long a certificate can be valid? Our systems runs for many years without user intervention and we'd like to keep it that way.
The format for certificates includes an expiry date which is encoded with ASN.1 type
GeneralizedTime. The latter is good until year 9999 (inclusive). However, some poorly written software may have trouble with dates beyond January 19th, 2038. If you control the client code, then you can choose a SSL library that does not have such problems. In general, the SSL implementation in Windows does not suffer from the Y2038 issue, and works fine with certificates valid for a thousand years.
The official reason why certificates expire is to keep CRL small. CRL are used for revocation. Revocation is a damage containment mechanism: this is used to invalidate a certificate whose private key has been stolen. If there is no revocation mechanism, then an attacker who compromised a server once will be able to run a fake server, that all clients will accept as genuine, until the certificate expiration.
If your certificates are valid for 1000 years, and you don't use revocation, then a compromised server becomes a problem that won't solve itself for 1000 years. On the other hand, if you use revocation, then the regularly issued CRL will include the list of revoked certificates; more precisely, a CRL is the list of the serial numbers of certificates which have been revoked and are not expired yet. To prevent the CRL from growing indefinitely, expired certificates are removed from the CRL (in that sense, revocation is just "early expiration"). But this works only if certificates really expire.
Either way, certificate expiration can be useful, and must be well thought about.
(As a side note, all of this implies that clients and servers shall have a reasonably accurate notion of the current date and time -- and by "accurate" I also mean that there shall be no method by which an attacker who is in control of the network could make clients or servers assume a wrong current time.)
Must a CA-server be available? (No Internet access)
Revocation is regular publication of fresh information about existing certificates. This can use CRL or OCSP, but, in any case, this information is short-lived (CRL publication is typically a daily operation) so some network access is needed at some point.
If server certificate issuance is a rare operation, then the CA could be split into an offline component, that is used manually to issue new certificates, and an online component (say, an OCSP responder), that answers requests from clients that want fresh revocation information.
Must clients have their own unique certificate?
In all of the above I talked about server certificates. In basic SSL, the server has a certificate, and the client knows that it talks to the real server. However, the server has no idea who the client is. A very common method (that you have used with your Web browser, e.g. whenever you bought something on Amazon) is to have the client send some authentication data (a "password") to the server -- this is safe because at that point, the SSL tunnel is up and running, and the client knows that it is talking to the genuine server.
SSL also supports client certificates, for mutual client-server authentication at the SSL level. This is conceptually justified when the server is not the entity that is responsible for defining who is a valid client and ascertaining their physical identity.
If, in your specific context, you can use a "show the password" model, then this will be a lot simpler to manage, because issuing certificates to all clients is often a neverending stream of nightmares.
If a device can act as both server and client, does it require multiple certificates?
Technically, the same certificate can be used for both roles, but care is needed.
A certificate is a binding between a public key and a name; software that validates a certificate needs to make sure that the certificate is a real one (signed by a trusted CA, not expired, not revoked...), and also that the name is the expected one. Usually, SSL clients, when they validate the server certificate, expect a specific server name (the one in the URL when the SSL really is HTTPS), and want that server name to appear in the certificate (this is specified in RFC 2818). So, with usual SSL libraries, you need the server certificates to include the DNS name of the server, as seen from the clients.
No such widespread convention exists in the other direction (server that validate client certificates), but the concept is still there and must be managed: all these games about certificates are about knowing who you are talking to, so names must be defined, properly recorded in the certificates, and verified.
You are theoretically free to use any naming convention as you see fit, but your SSL library may be more comfortable if, for the server-by-client validation, you use the "normal" way of having the server DNS name written in the server certificate.
Can the authorization part be solved using certificates or do we need to do that via a separate user access system?
No. Trying to do authorization with certificates only leads to sorrow and much grinding of teeth. Don't do that. Certificates are for authentication (knowing who you talk to), not for authorization (deciding what you should allow the authenticated peer to do).