Try reseting the PRam ( restart, on startup Hold down option, command, the leter P and the leter R. keep holding them down until you hear the start up chime for the 3rd time then you can let go)
If the machine is under warranty ( you can check here ) I would definetly not open the machine as you could end up voiding the Warranty.
Has the machine come in any contact with liquid by any chance?
If you have followed all the steps i have mentioned Then I agree that it is starting to sound like it is Hardware related, In which case i Think it might be worth while taking a visit to an AASP (Apple Authorised Service Provider), though it wont hurt to reset the PRAM again and reinstall the OS.
If It is out of warranty and you realy want to open it up yourself then the Keyboard flex is the wide flex to the left (if your looking at it) of the RAM, there is a Fine locking leaver on the oposite side of the connector to where the flex enters, that you will need to flip up. you could try giving the flex a light clean (maybe just use a pensil eraser). Once again I would strongly suggest you take the Machine to an AASP though as its likely you dont have the apropriate enviroment to open the machine without the risk of causing more damage .
Just out of curiosity when you reset SMC, PRAM, Boot into SafeBoot & Recovery, Were you able to use the built in keyboard to input the commands (eg P, R, Option, Command) or did you have to use the external?