I read that ANOVA and linear regression are the same thing. How can that be, considering that the output of ANOVA is some $F$ value and some $p$-value based on which you conclude if the sample means across the different samples are same or different.

But assuming the means are not equal (reject null hypothesis), ANOVA tells you nothing about the coefficients of the linear model. So how is linear regression the same as ANOVA?

ANOVA and linear regression are equivalent when the two models test against the same hypotheses and use an identical encoding. The models differ in their basic aim: ANOVA is mostly concerned to present differences between categories' means in the data while linear regression is mostly concern to estimate a sample mean response and an associated $\sigma^2$.

Somewhat aphoristically one can describe ANOVA as a regression with dummy variables. We can easily see that this is the case in the simple regression with categorical variables. A categorical variable will be encoded as a indicator matrix (a matrix of 0/1 depending on whether a subject is part of a given group or not) and then used directly for the solution of the linear system described by a linear regression.
Let's see an example with 5 groups. For the sake of argument I will assume that the mean of group1 equals 1,  the mean of group2 equals 2, ... and the mean of group5 equals 5. (I use MATLAB, but the exact same thing is equivalent in R.)

rng(123);               % Fix the seed
X = randi(5,100,1);     % Generate 100 random integer U[1,5]
Y = X + randn(100,1);   % Generate my response sample
Xcat = categorical(X);  % Treat the integers are categories

% One-way ANOVA
[anovaPval,anovatab,stats] = anova1(Y,Xcat);
% Linear regression
fitObj = fitlm(Xcat,Y);

% Get the group means from the ANOVA
ANOVAgroupMeans = stats.means
% ANOVAgroupMeans =
% 1.0953    1.8421    2.7350    4.2321    5.0517

% Get the beta coefficients from the linear regression
LRbetas = [fitObj.Coefficients.Estimate'] 
% LRbetas =
% 1.0953    0.7468    1.6398    3.1368    3.9565

% Rescale the betas according the intercept
scaledLRbetas = [LRbetas(1) LRbetas(1)+LRbetas(2:5)]
% scaledLRbetas =
% 1.0953    1.8421    2.7350    4.2321    5.0517

% Check if the two results are numerically equivalent
abs(max( scaledLRbetas - ANOVAgroupMeans)) 
% ans =
% 2.6645e-15


As it can be seen in this scenario the results where exactly the same. The minute numerical difference is due to the design not being perfectly balanced as well as the underlaying estimation procedure; the ANOVA accumulates numerical errors a bit more aggressively. To that respect we fit an intercept, LRbetas(1); we could fit an intercept-free model but that would not be a "standard" linear regression. (The results would be even closer to ANOVA in that case though.)

The $F$-statistic (a ratio of the means) in the case of the ANOVA and in the case of linear regression will be also be the same for the above example: 

abs( fitObj.anova.F(1) - anovatab{2,5} )
% ans =
% 2.9132e-13 


This is because procedures test the same hypothesis but with different wordings: ANOVA will qualitatively check if "the ratio is high enough to suggest that no grouping is implausible" while linear regression will qualitatively check if "the ratio is high enough to suggest an intercept only model is possibly inadequate".
(This is a somewhat free interpretation of the "possibility to see a value equal or greater than the one observed under the null hypothesis" and it is not meant to be a text-book definition.)

Coming back to the final part of your question about "ANOVA tell(ing) you nothing about the coefficients of the linear model (assuming the means are not equal") I hope you can now see that the ANOVA, in the case that your design is simple/balanced enough, tells you everything that a linear model would. The confidence intervals for group means will be the same you have for your $\beta$, etc. Clearly when ones starts adding multiple covariate in his regression model, a simple one-way ANOVA does not have a direct equivalence. In that case one augments the information used to calculate the linear regression's mean response with information that are not directly available for a one way ANOVA. I believe that one can re-express things in ANOVA terms once more but it is mostly an academic exercise.

An interesting paper on the matter is Gelman's 2005 paper titled: Analysis of Variance - Why it is more important than ever. Some important points raised; I am not fully supportive of the paper (I think I personally align much more with McCullach's view) but it can be a constructive read.

As a final note: The plot thickens when you have mixed effects models. There you have different concepts about what can be considered a nuisance or actual information regarding the grouping of your data. These issues are outside the scope of this question but I think they are worthy of a nod. 
