I am trying to implement VQE in pyQuil and am dumbfounded by how to measure the expectation value of a general Hamiltonian on $\mathbb{C}^{2^n}$ i.e. determine $\langle\psi , H \psi\rangle$ on a Quantum computer. As far as I understand on a real Quantum Computer (not any quantum virtual machine) I can only measure in the computational basis, which is the basis of the Hamiltonian $H = X = \sum x \left|x\right>\left<x\right|$, but not for any Hamiltonian whose eigenvectors are not the computational basis. But how do I measure with any Hamiltonian that is not diagonal in the computational basis?
Sure I can measure e.g. some of the qubits in the $X$-basis instead of the $Z$-basis by applying a Hadamard gate to them, but this surely doesn't help me if I want to measure sth. non-local, i.e. if the ground-state of my hamiltonian is an entangled state.
On a maybe related note: Can I write any hamiltonian (hermitian matrix) as a Pauli decomposition? I know I can for a single qubit, but does this hold for multiqubits aswell?