I'm really interested in making a new application for iPhone, and I have some experience in objective-c. My main problem is the visual part. I want to have graphics like in Spy Mouse. Could this be achieved using simple 2D graphics? Or would I need to use 3D, and just show it from this perspective?
This is simple 2D graphics. If you don't have access to Photoshop, download GIMP, look up tutorials on YouTube or try google. Creating graphics like these takes creativity and some art skills, but it's absolutely not out of your reach. There's alot of tutorials on creating buttons or text with the effects used in the picture you posted, they'll teach you how to use layers and you should be able to piece together the effect you'll like.
You're starting out, so it'll take alot of time to create even the basic sprites, but don't get discouraged. All i can tell you is that the hardest part of this job, as an untrained artist, is to stay within a style you chose. Do pay attention to this and don't rush your work.
I see no reason that this could not be acomplished in a 2D environment using sprites. In fact, depending on implementation, gameplay, etc it might be easier to do with 2D and sprites.
It sounds to me like your problem is art work. You sound like a programmer, and that means that you need and artist. Or, you need to become an artist yourself.
With the correct assets (2D sprites, tilemap, etc) in place, making a game look like the screenshot you've attached is going to be a piece of cake (realitivly speaking and all other things being equal).