C&C is comments and critique.
Drawing non organic things is something I don't ever do. But since no one else is swooping in to help, I'll try to provide info as someone who attempted this and hopefully it helps somewhat.
What got me is a lack of design ref. After spending a lot of time on this, I realized I had no idea how the legs were supposed to connect. Do they protrude beyond the edge? Are they contained under the base of the cockpit?
I was trying to avoid this but I just can't translate what's in my head into pixel form with these sprites. 
The mind is really good about tricking you into thinking you have a visual plan, because it kind of fills in the blanks. An example I give often is this: "Imagine the original Game Boy." And people say they can see it perfectly! But when I ask them questions like, "How many speaker lines are there?" they realize their mental image isn't as clear as they think. (It's six. And they're like this \, not this / which is the next thing I ask. Then the same questions for the original Game Boy Advance.
) So even if you think you've got a solid idea of how this thing should look, draw the views bigger! If you only pixel it at this size, you'll lose some info and your brain may trick you.
There's a reason why things like this exist:
Jasmine model sheet. Linked because Xbawks HUEG!With only the front view on that image, are those things on her arms like bracelets? Or are they attached to the dress?
With only the front and side views, is that thing on her head a full circle, or
like this?With all the views there, we get a better picture. But usually it's STILL not enough, so more specific info is created about things that aren't immediately obvious just by looking at a turnaround
like this.Even if working solo, creating things like this can be incredibly helpful. Even just asking yourself questions you'd think someone unfamiliar with the work might ask can help you solidify this design.
As far as perspective goes, here are the side and front views with lines drawn:
The big thing I wondered about was the feet. To me, the mech appears to get taller when facing left. He has his foot very far out for the front view, but I figured that was for animation purposes. (So you could get away with just flipping) On his side view, you can see what I assume is the back leg. And both legs are lower than the mech's far back leg in the front view. Which may make sense, but left me wondering how tall should the mech be while just standing in 45 degrees? If you don't know the answer to this question, think about it! Stuff like this may be getting in your way without you realizing it. (I didn't even notice until I started trying to make the new rotation)
One last thing I recommend doing if you're not already is working in an animation program. I have the side view and front view as frames 1 and 3, and the inbetween on frame 2. So I can flip and put parts where I think they should be.
Here are my attempt's progress shots:
I started with getting the things I could visualize the easiest. The cockpit, and the front flap. Added two pixels to the window on top of the front view, to make it flow better when I flipped to the side view.
More work on the window.
I realized I was having trouble with the window, so I omitted it to work on later. (Looking back, the one above isn't bad, actually.)
I added the front flap to the side view. I wasn't sure if it'd actually be visible in that view (Does it stick out, or go straight down), but it felt right adding it there.
I updated the front flap on the sideview. This was the point I realized I had no idea how the legs work. The backview does describes how they connect pretty well, but I also noticed I couldn't read what the arms should be at all and couldn't really proceed without that info.
I made some very small touch ups on all feet/front flap on all the views to make them flow when flipped. I changed up a lot of the leg. I made the leg a pixel shorter in the side view. Again, it felt right while seeing it rotate.
I'll see if I can continue working on this. I'm posting now because I can't really figure out the gun/arms. (But I might just copy the metal storm design!)
Two final things:
I've got no idea how to proceed and every attempt since this has gone in the trash. 
Why not post those attempts? People will probably be more likely to help if you show the exact troubles you're having.
Finally: There's really no shame in using a sprite overlay. Especially when it's just one sprite. Both of the palettes you're using seem like they could be reused for other things in the game, so I wouldn't worry at all.
Edit: So... I kept working on it, just following Metal Storm's design for the stuff I didn't get. Have three more process pics with comments.
I added back the window from earlier, since I realized it wasn't so bad when I made the post. I flipped the front facing view, because the extended leg for that matched better with the view I was trying to make. It also reminded me of another thing your sprite overlay provides! The glare doesn't flip with the sprite! I moved the leg in the 45 view so it doesn't protrude as much, since the back view makes it seem like that's how it's supposed to be.
I made the side view taller again. (I'm so fickle...
) I realized keeping all the bottom most feet on the same line is probably okay. Moved the "fins" on top back, and defined them a bit more. Added glare to the window. Added a gun. I decided this place would be best when flipped, since if the gun was the closer arm it would obscure more of the sprite. One other change: I extended the canvas 2 pixels to the left to make room for the gun. Don't worry, it's still two sprites! Just offset differently.
Made the gun have a black area on all the other frames. Again, you'll notice the side view takes up the extra space on the left of the canvas. But still two sprites. The gun looks much better for the middle view, just changing pixels until I got a look. Finally slowed down the animation timing! Took me 8 other versions to realize it might be too fast on the forum.
I'm still not happy with the "fins" or the far leg on the 45 view, but I've put enough time in this to give you some ideas! Also, I realize now I totally forgot the shoulder on the gun arm in the 45 view. *shrug* I just learned you already have the gun on part of the side view as well. I was only looking at the frames that are shown in the gifs for the longest time, sorry!
One other thing about working in animation software, is it's much easier to edit other frames. You'll see I did a lot of that to make everything mesh better. Sometimes when working on static frames, they get "sacred" and we want to leave them as they are.
Keep at it! On revision 2, I thought it wasn't going anywhere good and I wasn't going to post. It started to get good, but got hard again when I didn't know how the legs worked. So I stopped briefly, and picked it back up. I'm sure the attempts you've tried can be good with some work, sometimes you just have to push through the beginning stages you think are ugly. It's even worth saving those steps, because sometimes you realize you like them after you get away for a bit. (Like me with that window.)
All in all, hope this was helpful. I'm new to the art critique game. I know I'm long-winded.
