It would be worth checking with the host to see if they can either hook up an IP KVM or install a remote access card (IPMI, HP iLO, iDRAC, or RAS as appropriate) to provide an encrypted remote console.
With any FDE solution, you will necessarily have to have an unencrypted system bootstrap. At a minimum, this will consist of the MBR, bootloader, kernel, and initrd.
It is possible to network enable the FDE bootstrap system by using something like Mandos or using an entire OS installation and then switching to the real OS by remotely running custom scripts that utilise the power of pivot_root, chroot (or kexec) after cryptsetup and mount.
Using Xen and having a VM with encrypted storage is similar to using an entire OS for bootstrapping, but with less mucking around and easier maintenance. The only disadvantage in this approach is the virtualisation overhead.
The block device approach (LV, partition, or loopback) is certainly easy to get going, especially if you are trying to make the change on a production system.
Now the advice part: If you can get remote console access (full KVM, not serial) and you are building up a new machine, then go with FDE. All current distributions support it in the installer and it will be the least maintenance option.
Otherwise:
Don't even contemplate using FDE. A remote access bootstrap system will just be too fragile, and when it breaks, it will be a nightmare to fix. Don't try to convert a live system on the fly unless you really really really know what you are doing.
If you are building a new machine for this security upgrade and the virtualisation overhead is acceptable, then go for approach 2. It will be the most sane option for yourself and any other future sysadmin to understand/maintain. With this approach, you can use the OS provided installer encryption within the VM rather than encrypting the storage on the host if you want (pro/cons to both approaches wrt to maintenance/migration/etc).
If you have to make this change on the production system (which I highly recommend against. Make the client pay for a proper migration with a second system), then go with approach 3 and use a LUKS formatted block device (preferably a logical volume).
Under any of these scenarios, the base system or bootstrap code can obviously be trojaned so that the encryption key will be revealed. Don't waste your time trying to mitigate this risk unless you have a lot of time on your hands and your customer has money to burn. If you do have to mitigate it, then you would want to install something like Osiris.
Keep in the back of your mind that the data is going to be so much more at risk from software bugs, backup systems, misconfiguration, bad passwords, etc..