I was playing brawl for the first time yesterday and i had the worst first experience.

I was against people who had already played it for a day or two and had used the new characters and found who they liked.

One of them was Yoshi and ONLY uses Yoshi and has ALWAYS used Yoshi when playing in Melee too.

He just shield rolls, Down B's, and Smash B rollls.  AND DOESN't STOP.

Its impossible to hit him he down B's then rolls out of way, then does it again.

How do I kill him and show him that I'm still the best in the neighborhood.

Because I was In melee. 

Well, err, you should be able to hit him, I mean, if you're losing, that means he's winning, which means he's attacking too right? Just wait for the right moment and then attack when he's about to.
Or just refuse to play against him if he doesn't stop laming. :p

Use a character like Link or Samus who can grapple him from far away so as to catch him while he's in his egg rolling move.

Use Marth and counter.

 Will that work well???

Like amazingly well?

And what I meant by rolling was shield rolling, the dogde thingy. 

I'll use Ike and counter, and things like that. Since I really like Ike

just keep dodgeing him and grab items---like tap down and sheild to sidstep

on side note in SSE yoshi doing that makes the fights almost to easy