My Mac is stuck at the gray screen with Apple logo and spinning wheel

No you don't have to install Lion, unless there is nothing on the Lion Partition that you care for then you could do that and solve all your problems in one shot.

Another method is to hold shift key down while booting, this is Safe Mode and if you get in then you should copy out your files first thing to a external drive.

Then reboot normally and see if that fixed it.

Read this article as well, it assists a lot.

https://support.apple.com/kb/TS2570

Do you have a progress bar as well?

https://support.apple.com/kb/TS3148

Did you install anything recently? Like a program?

Have you used Disk Utility to Repair Disk and Repair Permissions on the MacIntosh HD/Lion Partition?

When you tried to install Ubuntu, it messed up your MBR portion of your GPT, which it mistakes for a full MBR like Windows.

https://en.wikipedia.org/wiki/GUID_Partition_Table

It also installs a Ubuntu swap folder in your EFI partition, which the machine tries to load into the ROMs I believe that that's likely responsible for your progress bar when you boot into Safe Mode.

You got to get that Ubuntu folder out of the EFI partition and that's no easy task, plus you go other things messed up.

Well you got your files off the machine, so your set to just erase the mess and get back to factory Lion.

Your going to need to make a Lion Recovery USB on someone else's Lion Mac using this software from Apple

Use a 1GB+ USB thumb drive, use Disk Utility to format it Partition Tab: 1 Partition, Option: GUID, format: OS X extended journaled and click Apply.

Next run this software, it will copy their Lion Recovery Partiton to your USB thumb drive

https://support.apple.com/kb/dl1433

Take it to your Mac, hold option and boot off the USB, use Disk Utility and select your entire physical hard drive, not just the indented Macintosh HD, you want the "500GB Toshiba 5934539583 media" that's on the far left.

Change the drive format under the Partition tab to 1 partition, Option: MBR, format MSDOS and click apply, (ensure you delete the old EFI partition) then

Erase Tab> Security Option Zero All Data, this will wipe off all data and check the drive for failing sectors, takes some time, so wait.

Format it under the Partition Tab: 1 partition, Option GUID, format OS X Extended journaled. (this is what Lion needs, new EFI partition created) give it the name MacIntosh HD and click Apply.

Quit Disk Utility and install the Lion Recovery Partition onto the internal drive.

Reboot the machine holding the command and r keys and enter the Lion Recovery, use your AppleID and password to download and install Lion into the Lion Macintosh HD

Once through Lion setup, install all your programs as you can, then last files from backup.

Good Luck 🙂

And before you ask, no you can't use the present Lion Recovery Parttiion to reinstall Lion onto the MacIntosh HD, your hidden EFI partiton is messed up from the Ubuntu cd, so you need to erase the hidden EFI partition and the entire drive in the process and that can only be done while booted from a external source, like the Lion Disk Assistant USB key you need to make.

Since you can't boot into Lion on your machine, you can't download and use the Lion Disk Assistant to make a copy of your own Lion Recovery Partition yourself, so you need someone else's Lion Mac to do that.

If you can't borrow anothers Lion Mac, your going to have to buy the $69 Lion USB thumb drive from Apple and follow the same steps as above. 😟

Good Luck 🙂