2007 G35 (under the hood it is a 2008) get in the car then dash shows the foot on brake and then start. Put foot on brake, push the start button - sometimes it starts sometimes it does not. Everything else appears to be working - windows, dash board, shows to be in park, door locks, brake lights work. Just does not always start. No clicking sounds from starter. What is wrong with me?

few things to try.
have someone verify or use a mirror or window to see if your brake lights come on when you are hitting the brake pedal and it doesn't start.
try to start it in neutral instead of park.
you say it works sometimes, so then I would try wiggling the gear shift lever forward or back to see if that changes it when it doesn't start, or pressing harder on the brake pedal.

checking if the brake lights turn on is for the brake light switch.
the neutral check is if the adjustment for the park/neutral switch is off.

Have you checked all the fuses under the hood? I had the same issues an it was a fusible link it was a red fuse looks like this