Clicking while pedaling I recently purchased a 2nd hand bike, and I am facing a clicking noise when I pedal (under slightly higher than normal load). I feel it almost as a pair of clicks in both pedals, and I feel one click when one pedal is ahead and another click when the other one is ahead (1 click when each pedal is at 5'o'clock position and I add weight on it)

What I tried.
1) I noticed this first after changing the pedals, so i changed it back, tightened the pedals multiple times but it persists.
2) I tightened the screws on the cranks/chain rings (spider to chain ring) (they were quite quite loose) but it didnt seem to help (Are both the chain rings held with the same screws? I use the little chainring only)
3) I tightened the 8mm hex holding the crank arms itself. Also didnt seem to help.

2) and 3) Seemed to get loosened after the ride, so I wonder if they are indeed the problem. I have tightened them tighter now, hope to see in the next ride.

I have not done anything with the BB yet. 

What else to look at, what can I do/try? Makes my bike feel very cheap :P I want to fix this.
If the click is felt in both pedals the problem is likely to be the bottom bracket bearings.

You should be able to feel bearing stiffness, roughness or 'notchiness' be turning the crank manually. It helps if you can get the chain off the rings to do this so the crank turns freely. Also check for any play of the crank axle in the bearings.

If the crank axle is not turning smoothly in the bearings or there is excessive play you likely need a new cartridge bottom bracket unit. These are not expensive but require special tools to take off the cranks and extract/install a new BB unit.

It's a bit worrying that you are finding loose bolts all over your drive train. You should probably do a complete drive train checkup to make sure there are no other lurking problems.

The cranks bolts are of special concern. If the alloy crank arms come loose on the steel axle taper they can be terminally damaged in short order. The bolts can be removed (the crank will stay on the axle), the bolt and internal thread in the axle should be cleaned and de-greased then the bolts -re-installed with non-permanent thread locker (e.g., blue Loctite) and torqued to proper specification. (This will of course all get done if you replace your bottom bracket cartridge.)