Cycles Compute Device: None (Not even CPU option)
Download the official version from the Blender website.

As it turns out the problem was with the Ubuntu Software Center version of Blender which for some reason doesn't offer the CUDA option. I downloaded the official version from the website and the option is available and I can render using my GPU.