If the on-line component goes anywhere beyond the ability to sync an opaque binary blob that only your local machines can decrypt and reencrypt, there's a problem there.
The devices could exchange their keys through a secure connection - be it direct (Bluetooth, LAN) or routed by a third-party service. It could also be transferred physically (through removable storage, or through retyping a bunch of numbers shown on one device into another device).
