If it's just two players bashing each other, it should be pretty easy. I would go about it like this: first I would focus on just getting a player on screen and then get it moving, perhaps even add an animation for the "hitting" part. Then I would get the collision detection working so you actually have some working game mechanic. After that I would create a tilemap so I have a "level" and add better animation.
I would suggest looking into LibGDX. That way you don't have to write your own texture loader or tilemap loader and you can focus on learning how to make games.
There's a nice, basic "hello world" type game on the wiki and some tutorials on youtube on libgdx to get you started.
Ok thanks, I'm glad that it doesn't sound too difficult, I'll want to make it more advanced eventually, but I thought that this would be a good starting point.
Also would I be correct in thinking that by using libGDX I could make it an android game? Because I would certainly like to do that.